Poj1122

题目大意：也是求最短路的题，有多个起始点，每个点按时间从小到大，输出路径等。

算法思路：dijikstra算法的应用。但是注意一下路径的输出，这里可以用记录每个点前驱的方法，来做，最后只要通过while循环(递归也可以)从结束点不断的寻找前驱即可。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
int n;
int a[25][25];
int ans[25][25],dist[25],pre[25];
bool visited[25];

int f,ff,sumf;
typedef struct Node
{
    int t;
    int src;
    int fw[25];
    int paths;
};
Node nodes[25];
bool cmp(Node n1,Node n2)
{
    return n1.t<n2.t;
}
void dijkstra(int src,int flag)
{
    memset(dist,0x3f,sizeof(dist));
    memset(visited,false,sizeof(visited));
    memset(pre,0,sizeof(pre));
    for(int i=1;i<=n;i++)
    {
        dist[i]=a[src][i];
    }
    for(int i=1;i<=n;i++)
    {
        if(i!=src)
            pre[i]=src;
    }

    visited[src]=true;
    for(int i=1;i<=n;i++)
    {
        int MIN=INF,node=-1;
        for(int j=1;j<=n;j++)
        {
            if(MIN>dist[j]&&!visited[j])
            {
                MIN=dist[j];
                node=j;
            }
        }
        if(node==-1)
            return ;
        visited[node]=true;
        if(node==f)
        {
             nodes[flag].t=dist[f];
             return;
        }


        for(int j=1;j<=n;j++)
        {
            if(!visited[j]&&dist[j]>dist[node]+a[node][j])
            {
                pre[j]=node;
                dist[j]=dist[node]+a[node][j];

            }

        }
    }
    nodes[flag].t=dist[f];

}
void getPath(int k)
{
    int ss=1;
    int fl=f;
    do
    {
        nodes[k].fw[ss++]=fl;
        fl=pre[fl];
    }while(fl);
    nodes[k].paths=ss-1;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
            if(a[i][j]==-1)
                a[i][j]=INF;
        }
    }
    sumf=1;
    scanf("%d",&f);
    getchar();
    while(true)
    {
        scanf("%d",&ff);
        char c=getchar();

        nodes[sumf++].src=ff;
        if(c=='\n')
            break;
    }

    for(int i=1;i<=sumf;i++)
    {
        int k=0;
        dijkstra(nodes[i].src,i);//第个起点
       getPath(i);
    }
    sort(nodes,nodes+sumf,cmp);

    printf("Org\tDest\tTime\tPath\n");
    for(int i=1;i<=sumf-1;i++)
    {
        printf("%d\t%d\t%d\t",nodes[i].src,f,nodes[i].t);
         for(int j=nodes[i].paths;j>=1;j--)
        {
            printf("%d\t",nodes[i].fw[j]);
        }
        printf("\n");
    }
return 0;

}