最短距离和路径问题 ford
题目描述
P1386 - 最短距离和路径问题 - 快乐信奥网
http://47.108.154.71/problem.php?id=1386
思路
ford+father数组来记路径，详见代码
代码
#include <bits/stdc++.h>
using namespace std;
int d[10010],n,m,s,k,fa[10010];
struct Theedge
{
int start,end,data;
}edge[10010];
void dfs(int xuss)
{
if(fa[xuss]!=0)
{
dfs(fa[xuss]);
}
cout<<xuss<<" ";
}
int main()
{
cin>>n>>m>>s>>k;
for(int i=1;i<=m;i++)
{
cin>>edge[i].start>>edge[i].end>>edge[i].data;
}
for(int i=1;i<=n;i++)
{
d[i]=100000;
}
d[s]=0;
for(int i=1;i<=n-1;i++)
{
for(int j=1;j<=m;j++)
{
int x=edge[j].start;
int y=edge[j].end;
int z=edge[j].data;
d[y]=min(d[y],d[x]+z);
if((d[x]+z)<=d[y])
{
fa[y]=x;
}
d[x]=min(d[x],d[y]+z);
if((d[y]+z)<=d[x])
{
fa[x]=y;
}
}
}
if(d[k]==100000)
{
cout<<"can't arrive";
}
else
{
cout<<d[k]<<endl;
dfs(k);
}
return 0;
}