记录编号	395648	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	这是一个响亮的昵称	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2017-04-16 21:37:07	内存使用	0.35 MiB

#include <fstream>
using namespace std;

ifstream input("djs.in");
ofstream output("djs.out");

bool color[100];
int key[100];
int path[100][100];
int father[100];
int n,m,v;
void dijkstra(int v)
{
    int i,j,u,Min;
    key[v]=0;
    for(i=0;i<n;i++)
    {
        Min=0xfffffff;
        for(j=0;j<n;j++)
            if(color[j]==false&&key[j]<Min)
            {u=j;Min=key[j];}
        color[u]=true;
        for(j=0;j<n;j++)
            if(path[u][j]!=0&&color[j]!=true&&key[j]>(path[u][j]+key[u]))
            {
                key[j]=path[u][j]+key[u];
                father[j]=u;
            }
    }
}
void print(int i)
{
    if(father[i]==-1)
    {
       output<<i<<" ";
       return;
    }
    else
        print(father[i]);
    output<<i<<" ";
}
int main()
{
    input>>n>>m>>v;
    int a ,b;
    int i;
    for(i=0;i<m;i++)
    {
        input>>a>>b;
        input>>path[a][b];
    }
    for(i=0;i<n;i++)
    {
        father[i]=-1;
        key[i]=0xfffffff;
    }

    dijkstra(v);
    for(i=0;i<n;i++)
    {
        output<<i<<":"<<endl;
        if(father[i]==-1)
            output<<"no"<<endl;
        else
        {
            output<<"path:";
            print(i);
            output<<endl;
            output<<"cost:"<<key[i]<<endl;
        }
    }
}