描述
给定n个顶点的带权有向图，若从顶点x到顶点y之间存在一条路径，那么这条路径的长度定义为路径上各条边的权值之和。
现在请你找出从顶点1到顶点n的一条最短路径。
输入
第一行为两个正整数n和m（n<=1000，m<=5000），n表示顶点数，m表示边数。
接下来有m行，每行三个正整数x，y，w，表示顶点x到y有一条边权为w的边。
1<=x, y<=n，w不大于10000。
两个顶点之间可能存在多条边。
输出
如果存在最短路径，则第一行输出最短路径长度，否则输出Sorry。
如果最短路径存在则在第二行输出一条从顶点1到顶点n之间的一条最短路径，格式如下：
1->v1->...->n
样例输入
4 4
1 2 3
2 3 1
2 4 4
3 4 2
样例输出
6
1->2->3->4
题解：难蚌，信奥一本通上说pre[x]来记录路径，结果代码示例的时候给我来个二维的数组，整蒙了，翻看了网上的各个代码再加上自己的排列组合才得出正确代码。。。
总结：
1.使用dijstra求最短路径时pre数组要提前设定好将pre[起点] = 0；
2.pre的更新是在dijstra更新每个点的最短距离dis[j]时，对于j点的前驱节点要更新为当前最短路节点 pre[j] = pos
3.输出最短路径时先输出起点，然后将终点传入print(终点)
4.在print方法中因为我们提前设定好了pre[起点] =0，所以递归的边界为if(pre[x]==0)return;否则继续调用，并将pre[x]传入，递归到边界返回时就可以输出每个节点了
5.对于pre[x]的意思指的是第x个节点的前驱节点；
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e8+10;
int n,m,k;
int ma[1001][1001],dis[1001],vis[1001],pre[1001];
//ma地图，dis起点到某个点的距离，vis标记，pre记录每个下标节点的前驱节点
void print(int x)
{
if(pre[x]==0)return;
print(pre[x]);
cout<<"->"<<x;
}
void dijstra(int st)
{
int pos=1,minn,sum=0;
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
dis[i] = ma[st][i]; //标记起点st到每个点i的距离dis[i]
pre[i] = st;
}
vis[st] = 1; //标记起点st已走过
dis[st] = 0; //将起点st距离设为0
pre[st] = 0; // 将起点设为0，作为递归边界
for(int i=1;i<=n;i++)
{
minn = inf;
for(int j=1;j<=n;j++) //找到当前起点到下一个点的最短距离minn及点位pos
{
if(vis[j]==0&&minn>dis[j]) //如果j点没走过且当前最小值大于dis[j]
{
minn = dis[j]; //更新minn
pos = j; //记录当前最小值下标j
}
}
if(minn==inf)break; //没有下一个点
vis[pos] = 1; //将当前最短路径点pos标记
//ans[++k] = pos;
for(int j=1;j<=n;j++)
{
if(vis[j]==0&&dis[j]>dis[pos]+ma[pos][j])
{
dis[j] = dis[pos]+ma[pos][j];
pre[j] = pos; //记录j节点的前驱节点是pos
}
}
}
}
int main()
{
cin>>n>>m;
memset(pre,0,sizeof(0));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i==j) ma[i][j] = 0;
else ma[i][j] = inf;
}
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
if(ma[a][b]>c) ma[a][b] = c;
}
dijstra(1);
if(dis[n]!=inf){
cout<<dis[n]<<endl<<1; //输出起点
print(n);//把终点传入，输出路径
}
else cout<<"Sorry";
return 0;
}
标签：pre,int,路径,pos,最短,dijstra,dis From： https://www.cnblogs.com/jyssh/p/16775805.html