pku 2394

 2009年7月25日

题目链接：PKU 2394 Checking an Alibi 
 
 分类：最短路

题目分析与算法原型
         其他没什么，就是需要注意重边的处理，Dijkastra就行了

Code:

 1#include<stdio.h>
 2#include<string.h>
 3#define len 505
 4#define max 0x7fffffff
 5
 6int f,p,c,m,i,j,map[len][len],dis[len],flag[len],cow[len],u,res[len],pos;
 7
 8void init()
 9{
10    for(i=1;i<=f;i++)
11        for(j=1;j<=f;j++)
12        {
13            if(i==j)map[i][j]=0;
14            else map[i][j]=max;
15        }
16}
17
18void dij(int v0)
19{
20    for(i=1;i<=f;i++)dis[i]=map[v0][i];
21    flag[v0]=1;
22    for(i=1;i<f;i++)
23    {
24        int min=max;
25        for(j=1;j<=f;j++)
26            if(flag[j]==0&&dis[j]<min)
27            {
28                u=j;
29                min=dis[j];
30            }
31        if(min==max)return ;
32        flag[u]=1;
33        for(j=1;j<=f;j++)
34            if(flag[j]==0&&map[u][j]<max&&dis[u]+map[u][j]<dis[j])
35                dis[j]=dis[u]+map[u][j];
36    }
37}
38
39int main()
40{
41    while(scanf("%d%d%d%d",&f,&p,&c,&m)!=EOF)
42    {
43        init();
44        memset(flag,0,sizeof(flag));
45        int a,b,cost;
46        for(i=1;i<=p;i++)
47        {
48            scanf("%d%d%d",&a,&b,&cost);
49            if(cost<map[a][b])
50            {
51                map[a][b]=cost;
52                map[b][a]=cost;
53            }
54        }
55        for(i=1;i<=c;i++)
56        {
57            int num;
58            scanf("%d",&num);
59            cow[i]=num;
60        }
61        dij(1);
62        pos=0;
63        for(i=1;i<=c;i++)
64            if(dis[cow[i]]<=m)res[pos++]=i;
65
66        printf("%d\n",pos);
67        for(i=0;i<pos;i++)printf("%d\n",res[i]);
68    }
69    return 0;
70}
71

posted on 2009-07-25 10:53 蜗牛也Coding 阅读(148) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2009年7月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜