锐客网

  1. 首页 > it技术 > >

poj 3268一道最短路径题

这个题目有一个很巧妙的转换方法。
众所周知，迪杰斯特拉算法是求单源最短路的，是一个点到多个点的最短路径
这个题目给你的图是的路都是单向的路。
而这题先让你求多个点到单个点的最短路，然后再求单个点到多个点的最短路。


求多个点到单个点（代号为s）的最短路在无向图中直接就是s到其他多个点的最短路，可是在有向图中不是这样。
【poj 3268一道最短路径题】那怎么求呢？
脑洞方法：把这个图上所有的单向路全都反过来，以s为起点跑一遍dijstra就可以了，跑出来的结果就是多个点到s这个点的最短路的结果。
正确性也很简单，就和无向图的正确性证明方法一样。


也就是这个题要跑两边最短路。然后按照要求输出结果就可以了。
AC代码：

#include #include #include #include #include using namespace std; const int maxn=1e3+10; const int inf=0x3f3f3f3f; int N,M; int st; int mp1[maxn][maxn]; int mp2[maxn][maxn]; bool settled[maxn]; int dis1[maxn]; int dis2[maxn]; void print(int m[maxn][maxn]) { for(int i=1; i<=N; i++) { for(int j=1; j<=N; j++) { if(j-1) printf(" "); printf("%5d",m[i][j]); } printf("\n"); } printf("\n"); } void dijinitial() { memset(settled,0,sizeof(settled)); memset(dis1,0,sizeof(dis1)); memset(dis2,0,sizeof(dis2)); settled[st]=1; for(int i=1; i<=N; i++) { dis1[i]=mp1[st][i]; dis2[i]=mp2[st][i]; }} void dijstra() { int r=N-1; while(r--) { int s=0,temp=inf; for(int i=1; i<=N; i++) { if(!settled[i]&&temp>dis1[i]) { s=i; temp=dis1[i]; } } settled[s]=1; for(int i=1; i<=N; i++) { if(!settled[i]&&mp1[s][i]!=inf) { if(dis1[i]>dis1[s]+mp1[s][i]) dis1[i]=dis1[s]+mp1[s][i]; } } }memset(settled,0,sizeof(settled)); settled[st]=1; r=N-1; while(r--) { int s=0,temp=inf; for(int i=1; i<=N; i++) { if(!settled[i]&&temp>dis2[i]) { s=i; temp=dis2[i]; } } settled[s]=1; for(int i=1; i<=N; i++) { if(!settled[i]&&mp2[s][i]!=inf) { if(dis2[i]>dis2[s]+mp2[s][i]) dis2[i]=dis2[s]+mp2[s][i]; } } }} int main() { while(scanf("%d%d%d",&N,&M,&st)==3) { memset(mp1,0,sizeof(mp1)); memset(mp2,0,sizeof(mp2)); for(int i=0; i<=N; i++) for(int j=0; j<=N; j++) mp1[i][j]=mp2[i][j]=inf; int r=M; while(r--) { int t1,t2,t3; scanf("%d%d%d",&t1,&t2,&t3); mp1[t1][t2]=t3; //for coming back. mp2[t2][t1]=t3; //for going to the party. }dijinitial(); dijstra(); /*printf("1:\n"); for(int i=1; i<=N; i++) printf("%d ",dis1[i]); printf("\n"); printf("2:\n"); for(int i=1; i<=N; i++) printf("%d ",dis2[i]); printf("\n"); */ int maxx=-1; for(int i=1; i<=N; i++) { if(i==st) continue; if(maxx

稍微有些长……不好意思我的水平有限……

    推荐阅读


    上一篇：getline函数

    下一篇：致每一位亲爱的您