問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2394思路:
題目說的有點復雜，其實就是求單源最短路徑，Dijkstra算法
需要注意的是輸入可能有重邊
具體關(guān)于Dijkstra算法，參考算法導論，有詳細的證明
第一次寫該算法，一次AC o(∩_∩)o...哈哈
代碼:
1 /* dijkstra algorithm */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_F 501
6 #define MAX_C 101
7 #define INF 0x7FFFFFFF
8 int adj[MAX_F][MAX_F];
9 int pos[MAX_C];
10 int in[MAX_F], d[MAX_F];
11 int f, p, c, m;
12
13 void
14 init()
15 {
16 int i, from, to, cost;
17 memset(adj, 0, sizeof(adj));
18 scanf("%d %d %d %d", &f, &p, &c, &m);
19 for(i=0; i<p; i++) {
20 scanf("%d %d %d", &from, &to, &cost);
21 if(adj[from][to]==0 || adj[from][to]>cost)
22 adj[from][to] = adj[to][from] = cost;
23 }
24 for(i=1; i<=c; i++)
25 scanf("%d", pos+i);
26 }
27
28 void
29 dijkstra()
30 {
31 int i, j, k, cur;
32 memset(in, 0, sizeof(in));
33 for(i=1; i<=f; i++)
34 d[i] = INF;
35 d[1] = 0;
36 in[1] = 1;
37 for(j=1; j<=f; j++)
38 if(!in[j] && adj[1][j])
39 d[j] = adj[1][j];
40 for(i=2; i<=f; i++) {
41 cur = INF;
42 for(j=1; j<=f; j++)
43 if(!in[j] && d[j]<=cur) {
44 k = j;
45 cur = d[j];
46 }
47 in[k] = 1;
48 for(j=1; j<=f; j++)
49 if(!in[j] && adj[k][j] && d[k]!=INF)
50 if(d[j] > d[k]+adj[k][j])
51 d[j] = d[k]+adj[k][j];
52 }
53 }
54
55 void
56 output()
57 {
58 int i, n = 0;
59 for(i=1; i<=c; i++)
60 if(d[pos[i]] <= m) {
61 ++n;
62 pos[i] = -1;
63 }
64 printf("%d\n", n);
65 for(i=1; i<=c; i++)
66 if(pos[i] == -1)
67 printf("%d\n", i);
68 }
69
70 int
71 main(int argc, char **argv)
72 {
73 init();
74 dijkstra();
75 output();
76 }