zoj 1456 Minimum Transport Cost 最短路

   书上把这放在了bellman，但我觉得用floyd应该更加好写些

    注意一个坑人的地方，就是测试数据中有自己到自己，输出是单独的n，而不是n-->n

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define maxn 100
using namespace std;
int dis[maxn][maxn],p[maxn],n;
queue<int> q;
int d[maxn];
int near[maxn];
bool inq[maxn];
int way[2][maxn],K[2];
void path(int now,bool f)
{
    if(near[now]==now)return;
    else
    {
        path(near[now],f);
        way[f][K[f]++]=now;
    }
}
bool cmp(int a,int b,int c)//生成路径比较字典序大小
{
    K[0]=K[1]=0;
    path(a,0);
    path(b,1);
    way[0][K[0]++]=c;
    way[1][K[1]++]=c;
    int i;
    for(i=0;way[0][i]+way[1][i];i++)
    {
        if(way[0][i]>way[1][i])return 0;
        if(way[0][i]<way[1][i])return 1;
    }
    return 0;
}
int bellman(int v,int aim)
{
    if(aim==v)return 0;
    while(!q.empty())q.pop();
    for(int i=0;i<=n;i++)
    {
        near[i]=i;
        inq[i]=0;
        d[i]=100000000;
    }
    d[v]=0;q.push(v);
    int now,next,t;
    while(!q.empty())
    {
        now=q.front();q.pop();
        inq[now]=0;
        for(next=1;next<=n;next++)
        {
            if(next==now||next==v)continue;//防止产生环
            if(dis[now][next]!=-1&&(d[next]>(t=d[now]+dis[now][next]+p[now])||(d[next]==t&&cmp(now,near[next],next))))
            {
                d[next]=t;
                near[next]=now;
                if(inq[next])continue;
                q.push(next);
                inq[next]=1;
            }
        }
    }
    return d[aim]-p[v];
}
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        int i,j;
        for(i=1;i<=n;i++)
          for(j=1;j<=n;j++)
            scanf("%d",&dis[i][j]);
        for(i=1;i<=n;i++)
          scanf("%d",&p[i]);
        int v,u,t;
        while(~scanf("%d%d",&v,&u))
        {
            if(v==-1||u==-1)break;
            t=bellman(v,u);
            printf("From %d to %d :\n",v,u);
            printf("Path: %d",v);
            K[0]=0;
            if(u!=v)
            {
              path(u,0);
              for(int i=0;i<K[0];i++)
                printf("-->%d",way[0][i]);
            }
            printf("\nTotal cost : %d\n\n",t);
        }
    }
}