范沐垚


私信TA

用户名:dotcpp0614554

访问量:4473

签 名:

好大喜功

等  级
排  名 200
经  验 6481
参赛次数 0
文章发表 85
年  龄 18
在职情况 学生
学  校 看今夜 小楼灯宴
专  业 尽是良辰美眷

  自我简介:

沽名钓誉

#include<iostream>
#include<algorithm>
#include<cstring> 
using namespace std;

const int N=1e1+10;

int n,m;
int dis[N],g[N][N];    //dis存每个点到起点的最短距离    g存a到b的距离 
bool st[N];      //判断该点是否已经是最短距离 

int find()
{
	memset(dis,0x3f,sizeof dis);
	dis[1]=0;
	                              //初始化所有点距离都为无穷 ,起点距离为0 
	for(int i=0;i<n;i++)   //n个点循环n次 
	{
		int t=-1;
		for(int j=1;j<=n;j++)             //每次找出还未确定点中最短的点 
		{
			if(!st[j]&&(t==-1||dis[t]>dis[j]))
			t=j;
		}
		for(int j=1;j<=n;j++)                     //更新所有点的距离 
		dis[j]=min(dis[j],dis[t]+g[t][j]);
		st[t]=true;
	}
	if(dis[n]==0x3f3f3f3f)return -1;
	return dis[n];
 } 

int main(void)
{
	cin>>n>>m;
	memset(g,0x3f,sizeof g);
	while(m--)
	{
		int a,b,x;
		cin>>a>>b>>x;
		g[a][b]=min(g[a][b],x);    //保证a到b为最短,考虑a到b有多条边的情况 
	 } 
	 int t=find();
	 cout<<t<<endl;
	return 0;
}


 

0.0分

0 人评分

  评论区