记录编号	12195	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	yanzheng	是否通过	通过
代码语言	C	运行时间	0.031 s
提交时间	2009-09-06 10:49:11	内存使用	0.27 MiB

#include <stdio.h>

int n,m,v;
int g[101][101]={0};
int path[101]={0};
int vis[101]={0},dis[101]={0};
FILE *out;

void init()
{
    FILE *in;
    int i,j,c,k;
    in=fopen("djs.in","r");
    fscanf(in,"%d%d%d",&n,&m,&v);
    for(k=0;k<m;k++)
    {
        fscanf(in,"%d%d%d",&i,&j,&c);
        g[i][j]=c;
    }
    for(k=0;k<n;k++) dis[k]=20000;
    dis[v]=0;
}

void djs()
{
    int i,j,k,p,min;
    for(k=0;k<n;k++)
    {
        min=20001;
        for(i=0;i<n;i++)
            if(dis[i]<min && !vis[i])
            {
                min=dis[i];
                p=i;
            }
        vis[p]=1;
        for(i=0;i<n;i++)
            if(i!=p && dis[p]+g[p][i]<dis[i] && g[p][i]!=0)
            {
                dis[i]=dis[p]+g[p][i];
                path[i]=p;
            }
    }
}

void find(int cur)
{
    if(cur==v)
    {
        fprintf(out,"%d ",cur);
    }
    else
    {
        find(path[cur]);
        fprintf(out,"%d ",cur);
    }
    return;
}

void print()
{
    int i,j,k;
    for(k=0;k<n;k++)
    {
        fprintf(out,"%d:\n",k);
        if(dis[k]==20000 || k==v)
            fprintf(out,"no\n");
        else
        {
            fprintf(out,"path:");
            find(k);
            fprintf(out,"\n");
            fprintf(out,"cost:%d\n",dis[k]);
        }
    }
}

int main(void)
{
    out=fopen("djs.out","w");
    init();
    djs();
    print();
    return 0;
}