1 /************************************************************** 2     Problem: 1681 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:8 ms 7     Memory:872 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <cstring>12 #include <algorithm>13 #include <queue>14  15 using namespace std;16 struct edges{17     int next, to, v;18 } e[2500];19  20 struct heap_node{21     int v, to;22 } NODE;23 inline bool operator < (const heap_node &a, const heap_node &b){24     return a.v > b.v;25 }26  27 priority_queue <heap_node> h;28 int X, Y, Z, F, P, C, time;29 int first[505], tot, d[505];30 int ans[105], cnt;31  32 inline int read(){33     int x = 0, sgn = 1;34     char ch = getchar();35     while (ch < ‘0‘ || ch > ‘9‘){36         if (ch == ‘-‘) sgn = -1;37         ch = getchar();38     }39     while (ch >= ‘0‘ && ch <= ‘9‘){40         x = x * 10 + ch - ‘0‘;41         ch = getchar();42     }43     return sgn * x;44 }45  46 inline void add_edge(int X, int Y, int Z){47     e[++tot].next = first[X], first[X] = tot;48     e[tot].to = Y, e[tot].v = Z;49 }50  51 void add_Edges(int x, int y, int z){52     add_edge(x, y, z);53     add_edge(y, x, z);54 }55  56 inline void add_to_heap(const int p){57     for (int x = first[p]; x; x = e[x].next)58         if (d[e[x].to] == -1){59             NODE.v = e[x].v + d[p], NODE.to = e[x].to;60             h.push(NODE);61         }62 }63  64 void Dijkstra(int S){65     memset(d, -1, sizeof(d));66     while (!h.empty()) h.pop();67     d[S] = 0, add_to_heap(S);68     int p;69     while (!h.empty()){70         if (d[h.top().to] != -1){71             h.pop();72             continue;73         }74         p = h.top().to;75         d[p] = h.top().v;76         h.pop();77         add_to_heap(p);78     }79 }80  81 int main(){82     F = read(), P = read(), C = read(), time = read();83     for (int i = 1; i <= P; ++i){84         X = read(), Y = read(), Z = read();85         add_Edges(X, Y, Z);86     }87      88     Dijkstra(1);89     for (int i = 1; i <= C; ++i){90         X = read();91         if (d[X] != -1 && d[X] <= time)92             ans[++cnt] = i;93     }94     printf("%d\n", cnt);95     for (int i = 1; i <= cnt; ++i)96         printf("%d\n", ans[i]);97     return 0;98 }