BZOJ2100 [Usaco2010 Dec]Apple Delivery

浏览数：18 / 时间：2015年06月11日

水水更健康。。。话说回来，这真的是水题？T T

首先，容易想到：

令ans1 = t1为源，到s和t2的距离之和；ans2 = t2为源，到s和t1的距离之和

ans = min(ans1, ans2)

然后，开始写单元最短路。。。spfa。。。

 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 }

View Code(spfa)

于是，TLE！！！竟然卡spfa！！！我去！！！

改成Dijkstra就好了。

 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 }