poj 1122 FDNY to the Rescue! 最短路

   注意 路径有权值为0的……

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <cctype>
#define INF 1E9
#define pp pair<int,int>
#define mp make_pair
using namespace std;
int dis[21][21];
int d[21],near[21];
bool vis[21];
int n;
int dijkstra(int v)
{
    priority_queue<pp,vector<pp>,greater<pp> >q;
    memset(d,127,sizeof(d));
    memset(vis,0,sizeof(vis));
    d[v]=0;
    q.push(mp(d[v],v));
    pp now;
    int i,t;
    while(!q.empty())
    {
        now=q.top();q.pop();
        v=now.second;
        if(vis[v])continue;
        vis[v]=1;
        for(i=1;i<=n;i++)
        {
            if(dis[v][i]<0||d[i]<=(t=dis[v][i]+d[v]))continue;
            d[i]=t;
            near[i]=v;
            q.push(mp(d[i],i));
        }
    }
}
int order[21];
int cmp(int a,int b)
{
    return d[a]<d[b];
}
int main()
{
    int T,i,j,v,cnt,t;
   // scanf("%d",&T);
   // while(T--)
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
         for(j=1;j<=n;j++)
          scanf("%d",&dis[j][i]);
        scanf("%d",&v);
        cnt=0;
        bool flag=1;
        while(scanf("%d",&order[cnt++]))
        {
            while(!isdigit(t=getchar())) if(t=='\n'){flag=0;break;}
            if(!flag)break;
            ungetc(t,stdin);
        }
        dijkstra(v);
        sort(order,order+cnt,cmp);
        printf("Org\tDest\tTime\tPath\n");
        for(i=0;i<cnt;i++)
        {
            t=order[i];
            printf("%d\t%d\t%d\t",t,v,d[t]);
            while(t!=v)
            {
                printf("%d\t",t);
                t=near[t];
            }
            printf("%d\n",t);
        }
      //  if(T)puts("");
    }
}