您能帮我想想嘛？必有重赏

更新时间2019-02-03 12:35:12

描述

zpyzoj不知不觉就收录100道题啦！

C位zpyzoier从一中各地赶来机房参与庆典。一中此时被划分成了F个地区，标号1到F，还有P条双向道路连接着这些地区。通过这些道路需要花费一定时间

留给zpyzoier们赶往机房的时间不多了！他们必须在M秒内赶往位于节点1的机房，否则就会错过庆典！

给出一中的地图和zpyzoier们目前所处的位置，请判断哪些zpyzoier能赶到庆典。

输入格式

第一行输入四个整数F P C M

接下来P行每行三个整数描述一条路，起点，终点，通过时间

接下来C行每行一个整数，表示一个zpyzoier所在的地点

输出格式

第一行输出能赶往庆典的zpyzoier的数量

接下来从小到大输出他们的编号，每个zpyzoier占一行

样例一

input

7 6 5 8
1 4 2
1 2 1
2 3 6
3 5 5
5 4 6
1 7 9
1
4
5
3
7

output

4
1
2
3
4

限制与约定

1≤C≤100,1≤M≤70000,1≤F≤500,1≤P≤1000 1≤C≤100,1≤M≤70000,1≤F≤500,1≤P≤1000

时间限制：1s

空间限制：64MB

这个是按Usaco 2005改的(你们老师偷懒了)

题目有点小难度,你若真心要学习c语言,不建议直接参考别人的程序(最终你无论是考试还是比赛终要靠自己完成的),以下是我按网上C++改为C的,你参考下

#include<stdio.h>

#include <string.h>

////Usaco2005

int dist[1001][1001];

int ans[1001];

int min(int a,int b)

{

    return (a<b)?a:b; 

}

int main()

{

    int i,j,k,x,y,z;

    int n,m,c,t,len;

    memset(dist,127/3,sizeof(dist));

    for (i=1; i<=n; i++)dist[i][i]=0;

    scanf("%d%d%d%d",&n,&m,&c,&t);

    for(  i=1; i<=m; i++)

        {

            scanf("%d%d%d",&x,&y,&z);

            if (z<=t)

                {

                    dist[x][y]=min(dist[x][y],z);

                    dist[y][x]=dist[x][y];

                }

        }

    for (  k=1; k<=n; k++)

        for (  i=1; i<=n; i++)

            for (  j=1; j<=n; j++)

                if (i!=j)

                    if (dist[i][k]+dist[k][j]<dist[i][j])

                        dist[i][j]=dist[i][k]+dist[k][j];

    for (  i=1; i<=c; i++)

        {

            scanf("%d",&x);

            if (dist[x][1]>t) continue;

            ans[++len]=i;

        }

    for (  i=1; i<len; i++)

        for (  j=i+1; j<=len; j++)

            if(ans[i]>ans[j])

                {

                    t=ans[i];

                    ans[i]=ans[j];

                    ans[j]=t;

                }

    printf("%d ",len);

    for (  i=1; i<=len; i++)

        printf("%d ",ans[i]);

    return 0;

}

能啊，新百胜17787216022