题目大意 求多组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,m);
printf("Path: ");
next = n;
while(next != m)
{
printf("%d-->", next);
next = dis[next][m];
}
printf("%d
", next);
printf("Total cost : %d
",MAP[n][m]);
printf("
");
}
}
void init()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
int main()
{
// init();
while(cin>>N&&N)
{
input();
floyd();
solve();
}
}