題目大意 求多組i到j的最短路徑 并輸出字典序最小....

現在只會floyd的方式

利用dis[i][j] 表示i到j的路徑中i 后面的節點

更新是比較dis[i][j] dis[i][k].

記住這個就好 ，其余存法貌似會有問題。代碼如下：

#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <ctime> #include <algorithm> #include <iostream> #include <sstream> #include <string> #define oo 0x13131313 using namespace std; const int maxn=50+5; int N; int MAP[maxn][maxn]; int dis[maxn][maxn]; int w[maxn]; void input() {for(int i=1;i<=N;i++)for(int j=1;j<=N;j++)dis[i][j]=1000000000;memset(MAP,0,sizeof(MAP));memset(w,0,sizeof(w));for(int i=1;i<=N;i++)for(int j=1;j<=N;j++){int c;scanf("%d",&c);if(c==-1){MAP[i][j]=1000000000;}else MAP[i][j]=c;}for(int i=1;i<=N;i++){scanf("%d",&w[i]);} } int FIND(int a,int b) {if(dis[a][b]!=1000000000){return FIND(a,dis[a][b]);}else return b; } void floyd() {for(int i=1; i<=N; i++)for(int j=1; j<=N; j++)dis[i][j] = j;for(int k=1;k<=N;k++){for(int i=1;i<=N;i++)for(int j=1;j<=N;j++){int new_patl = MAP[i][k] + MAP[k][j] + w[k];if(MAP[i][j]>new_patl){MAP[i][j]=new_patl;dis[i][j]=dis[i][k];}else if(MAP[i][j]==new_patl){dis[i][j]=min(dis[i][j],dis[i][k]);}}} } void solve() {int CASE=0;int n,m;int next;while(cin>>n>>m&&(n!=-1&&m!=-1)){printf("From %d to %d :\n",n,m);printf("Path: ");next = n;while(next != m){printf("%d-->", next);next = dis[next][m];}printf("%d\n", next);printf("Total cost : %d\n",MAP[n][m]);printf("\n");} } void init() {freopen("a.in","r",stdin);freopen("a.out","w",stdout); } int main() {// init();while(cin>>N&&N){input();floyd();solve();} }

轉載于:https://www.cnblogs.com/zy691357966/p/5480360.html

總結

以上是生活随笔為你收集整理的【floyd存字典序路径】【HDU1385】【Minimum Transport Cost】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。