记录编号	42678	评测结果	AAAAWAWA
题目名称	旅行计划	最终得分	75
用户昵称	鷐栩	是否通过	未通过
代码语言	C++	运行时间	0.009 s
提交时间	2012-09-27 22:12:03	内存使用	4.08 MiB

#include<iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

struct Node
{
    int qi;    
    int z;
    int q;
}z[100001];
int d[100001],p[10001],n,m,v;
void fun(int x)
{
    if(p[x]!=v)
    {
        fun(p[x]);
    }
    cout<<x<<' ';
    return ;
}
void bel()
{
    int i,j;
    bool x=0;
    for(i=0;i<n;i++)
    {
        d[i]=99999;
        p[i]=v;
    }
   d[v]=0;
    for(i=0;i<n;i++)
    {
        x=0;
        for(j=0;j<m;j++)
            if(d[z[j].qi]!=99999&&d[z[j].z]>d[z[j].qi]+z[j].q)
            {
                p[z[j].z]=z[j].qi;
                d[z[j].z]=d[z[j].qi]+z[j].q;
                x=1;
            }
        if(x==0)break;
    }
    return ;
}
int main()
{
       freopen("djs.in","r",stdin);
    freopen("djs.out","w",stdout);
    int i;
    scanf("%d%d%d",&n,&m,&v);
   // cin>>n>>m>>v;
    for(i=0;i<m;i++)
//        cin>>z[i].qi>>z[i].z>>z[i].q;
    scanf("%d%d%d",&z[i].qi,&z[i].z,&z[i].q);
    bel();
     for(i=0;i<n;i++)
    {
        cout<<i<<':'<<endl; 
        if(d[i]==99999||i==v)
            cout<<"no"<<endl;
        else
        {
            cout<<"path:"<<v<<' ';
            fun(i);
            cout<<endl<<"cost:"<<d[i]<<endl;
        }
    }
     /*   for(i=0;i<n;i++)
    {
        cout<<p[i]<<' '<<d[i] <<' ' <<i <<endl;
         
    }*/
    
    //system("pause");
    return 0;
}