1 /************************************************************** 2     Problem: 2100 3     User: rausen 4     Language: C++ 5     Result: Time_Limit_Exceed 6 ****************************************************************/ 7   8 #include <cstdio> 9 #include <cctype>10 #include <cstring>11 #include <algorithm>12  13 using namespace std;14 const int N = 100005;15 const int M = 400005;16  17 struct edges {18     int next, to, v;19     edges() {}20     edges(int _next, int _to, int _v) : next(_next), to(_to), v(_v) {}21 }e[M];22  23 int n, m, s, T1, T2;24 int first[N], tot;25 int q[N], l, r, dis[N];26 bool v[N];27 int ans;28  29 inline int read() {30     int x = 0;31     char ch = getchar();32     while (!isdigit(ch))33         ch = getchar();34     while (isdigit(ch)) {35         x = x * 10 + ch - ‘0‘;36         ch = getchar();37     }38     return x;39 }40  41 inline void Add_Edges(int x, int y, int z) {42     e[++tot] = edges(first[x], y, z), first[x] = tot;43     e[++tot] = edges(first[y], x, z), first[y] = tot;44 }45  46 void spfa(int S) {47     memset(dis, 127 / 3, sizeof(dis));48     q[0] = S, dis[S] = 0, v[S] = 1;49     int p, x, y;50     for (l = 0, r = 0; l != (r + 1) % N; (++l) %= N) {51         p = q[l];52         for (x = first[p]; x; x = e[x].next)53             if (dis[p] + e[x].v < dis[(y = e[x].to)]) {54                 dis[y] = dis[p] + e[x].v;55                 if (!v[y])56                     v[y] = 1, q[(++r) %= N] = y;57             }58         v[p] = 0;59     }60 }61  62 int main() {63     int i, X, Y, Z;64     m = read(), n = read(), s = read();65     T1 = read(), T2 = read();66     for (i = 1; i <= m; ++i){67         X = read(), Y = read(), Z = read();68         Add_Edges(X, Y, Z);69     }70     spfa(T1);71     ans = dis[s] + dis[T2];72     spfa(T2);73     printf("%d\n", min(ans, dis[s] + dis[T1]));74     return 0;75 }

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