wzy的大冒险——出发咯QAQ

单点时限: 2.0 sec

内存限制: 512 MB

wzy踏上了冒险的旅程。
现在他从地精手里买了一份地图，地图上有n个城镇。
他从第一个城镇出发，走向（没钱只能走）第n个城镇，现在，请你帮wzy找到一条最短的路径，并倒序（从n到1）输出一条最短路径。
举个栗子:如果有两条路径6 4 3 1和6 5 2 1，我们选择6 4 3 1这条。
地精小提示：路是单向的QAQ。

输入格式

第一行两个数n,m ，(1≤n≤103,1≤m≤103)

接下来m行，每行三个数x,y,z，表示点 x 与点 y 之间有一条权值为 z 的有向边 (1≤x,y,z≤103).

输出格式

第一行一个整数表示 1 到 n 的最短距离；
第二行倒序输出这条路径。

样例

input

5 7
1 2 69
1 3 87
1 4 79
2 5 94
2 3 10
3 5 79
4 5 43

output

122
5 4 1

关键是利用d【maxn】数组去保存路径 然后进行输出  以及一些存图操作

#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1e3+10;
typedef long long ll;
int way[maxn][maxn];
int dis[maxn];
int flag[maxn];
int d[maxn]; 
int n,m;
int dijkstra()
{
	memset(dis,0,sizeof(dis));
	for(int i=1;i<=n;i++)
	{
		dis[i]=way[1][i];
		if(way[1][i]!=INF)
		{
			d[i]=1; 
		 } 
	}
	flag[1]=1;dis[1]=0;
	int x;
	for(int i=1;i<=n;i++) 
	{
		int ans=INF;
		for(int j=1;j<=n;j++)
		{
			if(ans>dis[j]&&!flag[j])
			{
				ans=dis[j];
				x=j;
			}
		}
		flag[x]=1;
		for(int i=1;i<=n;i++)
		{
			if(!flag[i])
			{
				if(dis[i]>dis[x]+way[x][i])
				{
					dis[i]=dis[x]+way[x][i];
					d[i]=x;
				}
			}
		 } 
	}
 }
 int main()
 {
 	cin>>n>>m;
 	for(int i=1;i<=n;i++)
 	{
 		for(int j=1;j<=n;j++)
 		{
 			way[i][j]=INF; 
		 }
	 }
	 for(int i=1;i<=m;i++)
	{
	 	int a,b,c;
	 	cin>>a>>b>>c;
	 	way[a][b]=c;
	}
	dijkstra();
	cout<<dis[n]<<endl;
	int t=n;
	cout<<n<<" ";
	int s=1;
	while(t!=1)
	{
		t=d[t];
		if(s)
		{
			cout<<t;
			s=0; 
		}
		else cout<<" "<<t; 
	 }
	 return 0;
  }