[kuangbin]带你飞之'最短路练习'专题

专题四最短路练习
√ POJ 2387 Til the Cows Come Home
√ POJ 2253 Frogger
√ POJ 1797 Heavy Transportation
√ POJ 3268 Silver Cow Party
√ POJ 1860 Currency Exchange
√ POJ 3259 Wormholes
√ POJ 1502 MPI Maelstrom
√ POJ 3660 Cow Contest
√ POJ 2240 Arbitrage
√ POJ 1511 Invitation Cards
√ POJ 3159 Candies
√ POJ 2502 Subway
√ POJ 1062 昂贵的聘礼
√ POJ 1847 Tram
√ LightOJ 1074 Extended Traffic
√ HDU 4725 The Shortest Path in Nya Graph
HDU 3416 Marriage Match IV
√ HDU 4370 0 or 1
√ POJ 3169 Layout

// poj 2387

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: ms
 4  * @Memory Limit: k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-10-25 08:14:08
 7  * @LastEditTime: 2019-10-25 08:25:39
 8  */
 9 #include<cstdio>
10 #include<cstring>
11 #include<cmath>
12 #include<iostream>
13 #include<string>
14 #include<algorithm>
15 #include<vector>
16 #include<queue>
17 #include<stack>
18 #include<set>
19 #include<map>
20 #define rep(i, n) for(int i=0;i!=n;++i)
21 #define per(i, n) for(int i=n-1;i>=0;--i)
22 #define Rep(i, sta, n) for(int i=sta;i!=n;++i)
23 #define rep1(i, n) for(int i=1;i<=n;++i)
24 #define per1(i, n) for(int i=n;i>=1;--i)
25 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
26 #define L k<<1
27 #define R k<<1|1
28 #define mid (tree[k].l+tree[k].r)>>1
29 using namespace std;
30 const int INF = 0x3f3f3f3f;
31 typedef long long ll;
32 
33 inline int read() {
34     char c=getchar();int x=0,f=1;
35     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
36     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
37     return x*f;
38 }
39 // -----------------------------------------------------
40 const int MAXN = 1000+5;
41 int T, n;
42 int G[MAXN][MAXN];
43 
44 int vis[MAXN], dis[MAXN];
45 
46 int dij() {
47     rep1(i, n) {
48         dis[i] = G[i][1];
49         vis[i] = 0;
50     }
51     vis[1] = 1;
52     rep(i, n-1) {
53         int minn = INF;
54         int t;
55         rep1(j, n) {
56             if(!vis[j] && dis[j] < minn) {
57                 minn = dis[j];
58                 t = j;
59             }
60         }
61         vis[t] = 1;
62         rep1(j, n) {
63             if(!vis[j] && dis[j] > dis[t] + G[t][j]) {
64                 dis[j] = dis[t] + G[t][j];
65             }
66         }
67     }
68     return dis[n];
69 }
70 
71 int main() {
72     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
73     int s, e, v;
74     while(cin >> T >> n) {
75         rep1(i, n) rep1(j, n) G[i][j] = INF;
76         rep(i, T) {
77             cin >> s >> e >> v;
78             if(v < G[s][e]) G[s][e] = G[e][s] = v;
79         }
80         cout << dij() << "
";
81     }
82     return 0;
83 }

View Code

// poj 2253

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: ms
 4  * @Memory Limit: k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-10-25 09:19:11
 7  * @LastEditTime: 2019-10-25 10:28:41
 8  */
 9 #include<cstdio>
10 #include<cstring>
11 #include<cmath>
12 #include<iostream>
13 #include<iomanip>
14 #include<string>
15 #include<algorithm>
16 #include<vector>
17 #include<queue>
18 #include<stack>
19 #include<set>
20 #include<map>
21 #define rep(i, n) for(int i=0;i!=n;++i)
22 #define per(i, n) for(int i=n-1;i>=0;--i)
23 #define Rep(i, sta, n) for(int i=sta;i!=n;++i)
24 #define rep1(i, n) for(int i=1;i<=n;++i)
25 #define per1(i, n) for(int i=n;i>=1;--i)
26 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
27 #define L k<<1
28 #define R k<<1|1
29 #define mid (tree[k].l+tree[k].r)>>1
30 using namespace std;
31 const int INF = 0x3f3f3f3f;
32 typedef long long ll;
33 
34 inline int read() {
35     char c=getchar();int x=0,f=1;
36     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
37     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
38     return x*f;
39 }
40 // -----------------------------------------------------
41 const int MAXN = 200+5;
42 
43 int n;
44 int x[MAXN], y[MAXN];
45 double G[MAXN][MAXN];
46 
47 bool vis[MAXN];
48 double dis[MAXN];
49 
50 double dij() {
51     rep(i, n) {
52         vis[i] = false;
53         dis[i] = G[i][0];
54     }
55     vis[0] = 1;
56     rep(i, n-1) {
57         double minn = INF;
58         int t;
59         rep(j, n) {
60             if(!vis[j] && dis[j] < minn) {
61                 minn = dis[j];
62                 t = j;
63             }
64         }
65         vis[t] = true;
66         rep(j, n) {
67             if(!vis[j]) {
68                 dis[j] = min(dis[j], max(minn, G[t][j]));
69             }
70         }
71     }
72     return dis[1];
73 }
74 
75 int main() {
76     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
77     int cnt = 1;
78     while(cin >> n && n) {
79         rep(i, n) x[i] = read(), y[i] = read();
80         rep(i, n) Rep(j, i, n) {
81             if(i == j) G[i][i] = INF;
82             else G[i][j] = G[j][i] = sqrt(double((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));
83         }
84         cout << "Scenario #" << cnt++ << "
";
85         //printf("Frog Distance = %.3f

", dij());
86         cout << "Frog Distance = " << fixed << setprecision(3) << dij() << "

";
87     }
88     return 0;
89 }

View Code

// poj 1797

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: ms
 4  * @Memory Limit: k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-10-25 11:00:57
 7  * @LastEditTime: 2019-10-25 14:04:36
 8  */
 9 #include<cstdio>
10 #include<cstring>
11 #include<cmath>
12 #include<iostream>
13 #include<string>
14 #include<algorithm>
15 #include<iomanip>
16 #include<vector>
17 #include<queue>
18 #include<stack>
19 #include<set>
20 #include<map>
21 #define rep(i, n) for(int i=0;i!=n;++i)
22 #define per(i, n) for(int i=n-1;i>=0;--i)
23 #define Rep(i, sta, n) for(int i=sta;i!=n;++i)
24 #define rep1(i, n) for(int i=1;i<=n;++i)
25 #define per1(i, n) for(int i=n;i>=1;--i)
26 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
27 #define L k<<1
28 #define R k<<1|1
29 #define mid (tree[k].l+tree[k].r)>>1
30 using namespace std;
31 const int INF = 0x3f3f3f3f;
32 typedef long long ll;
33 
34 inline int read() {
35     char c=getchar();int x=0,f=1;
36     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
37     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
38     return x*f;
39 }
40 // -----------------------------------------------------
41 const int MAXN = 1000+5;
42 
43 int n, m;
44 int G[MAXN][MAXN], dis[MAXN];
45 bool vis[MAXN];
46 
47 int dij() {
48     rep1(i, n) {
49         dis[i] = G[i][1];
50         vis[i] = false;
51     }
52     vis[1] = true;
53     rep(i, n-1) {
54         int maxnn = 0;
55         int t = -1;
56         rep1(j, n) {
57             if(!vis[j] && dis[j] > maxnn) { //!vis[j] && dis[j] != INF && dis[j] > maxnn
58                 maxnn = dis[j];
59                 t = j;
60             }
61         }
62         if(t == -1) break;
63         vis[t] = true;
64         rep1(j, n) {
65             if(!vis[j]) {
66                 dis[j] = max(dis[j], min(maxnn, G[t][j]));
67             }
68         }
69     }
70     return dis[n];
71 }
72 
73 int main() {
74     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
75     int T = read();
76     int cnt = 1;
77     int s, e, v;
78     while(T--) {
79         n = read(); m = read();
80         rep1(i, n) rep1(j, n) G[i][j] = 0; //G[i][j] = INF;
81         rep(i, m) {
82             s = read(); e = read(); v = read();
83             G[s][e] = G[e][s] = v;
84         }
85         cout << "Scenario #" << cnt++ << ":" << "
";
86         cout << dij() << "

";
87     }
88     return 0;
89 }

View Code

// poj 3268

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: ms
 4  * @Memory Limit: k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-10-25 14:25:52
 7  * @LastEditTime: 2019-10-25 15:51:43
 8  */
 9 #include<cstdio>
10 #include<cstring>
11 #include<cmath>
12 #include<iostream>
13 #include<string>
14 #include<algorithm>
15 #include<iomanip>
16 #include<vector>
17 #include<queue>
18 #include<stack>
19 #include<set>
20 #include<map>
21 #define read(n) n = input_i()
22 #define rep(i, n) for(int i=0;i!=n;++i)
23 #define per(i, n) for(int i=n-1;i>=0;--i)
24 #define Rep(i, sta, n) for(int i=sta;i!=n;++i)
25 #define rep1(i, n) for(int i=1;i<=n;++i)
26 #define per1(i, n) for(int i=n;i>=1;--i)
27 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
28 #define L k<<1
29 #define R k<<1|1
30 #define mid (tree[k].l+tree[k].r)>>1
31 using namespace std;
32 const int INF = 0x3f3f3f3f;
33 typedef long long ll;
34 
35 inline int input_i() {
36     char c=getchar();int x=0,f=1;
37     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
38     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
39     return x*f;
40 }
41 // -----------------------------------------------------
42 const int MAXN = 1000+5;
43 const int MAXM = 100000+5;
44 
45 int n, m, x;
46 int s[MAXM], e[MAXM], v[MAXM];
47 int G[MAXN][MAXN];
48 
49 int dis[MAXN];
50 int a1[MAXN], a2[MAXN];
51 bool vis[MAXN];
52 
53 void dij() {
54     rep1(i, n) {
55         vis[i] = false;
56         dis[i] = G[x][i];
57     }
58     vis[x] = true;
59     rep(i, n-1) {
60         int minn = INF;
61         int t = -1;
62         rep1(j, n) {
63             if(!vis[j] && dis[j] < minn) {
64                 minn = dis[j];
65                 t = j;
66             }
67         }
68         if(t == -1) break;
69         vis[t] = true;
70         rep1(j, n) {
71             if(!vis[j] && G[t][j] != INF && dis[j] > minn + G[t][j]) {
72                 dis[j] = minn + G[t][j];
73             }
74         }
75     }
76 }
77 
78 int main() {
79     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
80     while(cin >> n >> m >> x) {
81         rep1(i, n) rep1(j, n) G[i][j] = INF;
82         rep(i, m) {
83             read(s[i]); read(e[i]); read(v[i]);
84             if(v[i] < G[s[i]][e[i]]) G[s[i]][e[i]] = v[i];
85         }
86         dij();
87         rep1(i, n) a1[i] = dis[i];
88         rep1(i, n) rep1(j, n) G[i][j] = INF;
89         rep(i, m) {
90             if(v[i] < G[e[i]][s[i]]) G[e[i]][s[i]] = v[i];
91         }
92         dij();
93         rep1(i, n) a2[i] = dis[i];
94         int maxn = -1;
95         rep1(i, n) if(a1[i] != INF && a2[i] != INF && a1[i]+a2[i] > maxn) maxn = a1[i]+a2[i];
96         cout << maxn << "
";
97     }
98     return 0;
99 }

View Code

// poj 1860

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: ms
 4  * @Memory Limit: k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-10-25 16:51:13
 7  * @LastEditTime: 2019-10-25 20:25:55
 8  */
 9 #include<cstdio>
10 #include<cstring>
11 #include<cmath>
12 #include<iostream>
13 #include<string>
14 #include<algorithm>
15 #include<iomanip>
16 #include<vector>
17 #include<queue>
18 #include<stack>
19 #include<set>
20 #include<map>
21 #define read(n) n = read_n()
22 #define rep(i, n) for(int i=0;i!=n;++i)
23 #define per(i, n) for(int i=n-1;i>=0;--i)
24 #define Rep(i, sta, n) for(int i=sta;i!=n;++i)
25 #define rep1(i, n) for(int i=1;i<=n;++i)
26 #define per1(i, n) for(int i=n;i>=1;--i)
27 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
28 #define L k<<1
29 #define R k<<1|1
30 #define mid (tree[k].l+tree[k].r)>>1
31 #define eps 1e-10
32 using namespace std;
33 const int INF = 0x3f3f3f3f;
34 typedef long long ll;
35 
36 inline int read_n() {
37     char c=getchar();int x=0,f=1;
38     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
39     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
40     return x*f;
41 }
42 // -----------------------------------------------------
43 const int MAXN = 100+5;
44 const int MAXM = 200+5;
45 
46 int n, m, m2, x;
47 double sta;
48 
49 struct node {
50     int u, v;
51     double r, c;
52 } edge[MAXM];
53 
54 double dis[MAXN];
55 
56 bool Bellman_ford() {
57     bool flag;
58     rep(i, n-1) {
59         flag = false;
60         rep(j, m) {
61             if(dis[edge[j].v] < (dis[edge[j].u]-edge[j].c)*edge[j].r) {
62                 dis[edge[j].v] = (dis[edge[j].u]-edge[j].c)*edge[j].r;
63                 flag = true;
64             }
65         }
66         if(!flag) break;
67     }
68     flag = false;
69     rep(i, m) {
70         if(dis[edge[i].v] < (dis[edge[i].u]-edge[i].c)*edge[i].r) {
71             return true;
72         }
73     }
74     return false;
75 }
76 
77 int main() {
78     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
79     cin >> n >> m2 >> x >> sta;
80     m = 0;
81     rep(i, m2) {
82         cin >> edge[m].u >> edge[m].v;
83         cin >> edge[m].r >> edge[m].c;
84         ++m;
85         edge[m].u = edge[m-1].v;
86         edge[m].v = edge[m-1].u;
87         cin >> edge[m].r >> edge[m].c;
88         ++m;
89     }
90     rep1(i, n) dis[i] = 0;
91     dis[x] = sta;
92     if(Bellman_ford()) cout << "YES
";
93     else cout << "NO
";
94     return 0;
95 }

View Code

// poj 3259

  1 /*
  2  * @Promlem: 
  3  * @Time Limit: ms
  4  * @Memory Limit: k
  5  * @Author: pupil-XJ
  6  * @Date: 2019-10-26 00:52:36
  7  * @LastEditTime: 2019-10-26 01:40:33
  8  */
  9 #include<cstdio>
 10 #include<cstring>
 11 #include<cmath>
 12 #include<iostream>
 13 #include<string>
 14 #include<algorithm>
 15 #include<iomanip>
 16 #include<vector>
 17 #include<queue>
 18 #include<stack>
 19 #include<set>
 20 #include<map>
 21 #define read(n) n = read_n()
 22 #define rep(i, n) for(int i=0;i!=n;++i)
 23 #define per(i, n) for(int i=n-1;i>=0;--i)
 24 #define Rep(i, sta, n) for(int i=sta;i!=n;++i)
 25 #define rep1(i, n) for(int i=1;i<=n;++i)
 26 #define per1(i, n) for(int i=n;i>=1;--i)
 27 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
 28 #define L k<<1
 29 #define R k<<1|1
 30 #define mid (tree[k].l+tree[k].r)>>1
 31 #define eps 1e-10
 32 using namespace std;
 33 const int INF = 0x3f3f3f3f;
 34 typedef long long ll;
 35 
 36 inline int read_n() {
 37     char c=getchar();int x=0,f=1;
 38     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 39     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 40     return x*f;
 41 }
 42 // -----------------------------------------------------
 43 const int MAXN = 500+5;
 44 const int MAXM = 5200+5;
 45 
 46 int n, m1, m2;
 47 
 48 int num;
 49 struct node {
 50     int v, next;
 51     int w;
 52 } edge[MAXM];
 53 
 54 int head[MAXN];
 55 inline void add(int x, int y, int w) {
 56     edge[num].v = y;
 57     edge[num].next = head[x];
 58     edge[num].w = w;
 59     head[x] = num++;
 60 }
 61 
 62 int dis[MAXN], vis[MAXN], inq[MAXN];
 63 
 64 bool SPFA(int s) {
 65     queue<int> q;
 66     rep1(i, n) {
 67         dis[i] = INF;
 68         vis[i] = inq[i] = 0;
 69     }
 70     dis[s] = 0;
 71     vis[s] = inq[s] = 1;
 72     q.push(s);
 73     while(!q.empty()) {
 74         int u = q.front();
 75         q.pop();
 76         vis[u] = 0;
 77         for(int i = head[u]; i != -1; i = edge[i].next) {
 78             int v = edge[i].v;
 79             if(dis[v] > dis[u] + edge[i].w) {
 80                 dis[v] = dis[u] + edge[i].w;
 81                 if(!vis[v]) {
 82                     q.push(v);
 83                     vis[v] = 1;
 84                     ++inq[v];
 85                     if(inq[v] > n) return true;
 86                 }
 87             }
 88         }
 89     }
 90     return false;
 91 }
 92 
 93 int main() {
 94     //ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 95     int T = read_n();
 96     int s, e, v;
 97     while(T--) {
 98         read(n); read(m1); read(m2);
 99         rep1(i, n) head[i] = -1;
100         num = 0;
101         rep(i, m1) {
102             read(s); read(e); read(v);
103             add(s, e, v);
104             add(e, s, v);
105         }
106         rep(i, m2) {
107             read(s); read(e); read(v);
108             add(s, e, -v);
109         }
110         if(SPFA(1)) cout << "YES
";
111         else cout << "NO
";
112     }
113     return 0;
114 }

View Code

// poj 1502

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: ms
 4  * @Memory Limit: k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-10-26 15:10:47
 7  * @LastEditTime: 2019-10-26 15:50:27
 8  */
 9 #include<cstdio>
10 #include<cstring>
11 #include<cmath>
12 #include<iostream>
13 #include<string>
14 #include<algorithm>
15 #include<iomanip>
16 #include<vector>
17 #include<queue>
18 #include<stack>
19 #include<set>
20 #include<map>
21 #define read(n) n = read_n()
22 #define rep(i, n) for(int i=0;i!=n;++i)
23 #define per(i, n) for(int i=n-1;i>=0;--i)
24 #define Rep(i, sta, n) for(int i=sta;i!=n;++i)
25 #define rep1(i, n) for(int i=1;i<=n;++i)
26 #define per1(i, n) for(int i=n;i>=1;--i)
27 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
28 #define L k<<1
29 #define R k<<1|1
30 #define mid (tree[k].l+tree[k].r)>>1
31 #define eps 1e-10
32 using namespace std;
33 const int INF = 0x3f3f3f3f;
34 typedef long long ll;
35 
36 inline int read_n() {
37     char c=getchar();int x=0,f=1;
38     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
39     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
40     return x*f;
41 }
42 // -----------------------------------------------------
43 const int MAXN = 100+5;
44 int n;
45 int G[MAXN][MAXN];
46 
47 int dis[MAXN], vis[MAXN];
48 
49 int dij() {
50     rep1(i, n) {
51         dis[i] = G[i][1];
52         vis[i] = 0;
53     }
54     vis[1] = 1;
55     rep(i, n-1) {
56         int minn = INF;
57         int t = -1;
58         rep1(j, n) if(!vis[j] && dis[j] < minn) {
59             t = j;
60             minn = dis[j];
61         }
62         if(t == -1) break;
63         vis[t] = 1;
64         rep1(j, n) if(!vis[j] && dis[j] > dis[t] + G[t][j]) {
65             dis[j] = dis[t] + G[t][j];
66         }
67     }
68     int maxn = 0;
69     rep1(i, n) if(dis[i] != INF && dis[i] > maxn) maxn = dis[i];
70     return maxn;
71 }
72 
73 int main() {
74     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
75     cin >> n;
76     rep1(i, n) rep1(j, n) G[i][j] = INF;
77     int x;
78     Rep1(i, 2, n) {
79         Rep(j, 1, i) {
80             string num;
81             cin >> num;
82             if(num == "x") continue;
83             else {
84                 int x = 0;
85                 rep(k, num.size()) x = x*10 + num[k]-'0';
86                 G[i][j] = G[j][i] = x;
87             }
88         }
89     }
90     cout << dij() << "
";
91     return 0;
92 }

View Code

// poj 3660

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: ms
 4  * @Memory Limit: k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-10-26 16:15:10
 7  * @LastEditTime: 2019-10-26 17:00:11
 8  */
 9 #include<cstdio>
10 #include<cstring>
11 #include<cmath>
12 #include<iostream>
13 #include<string>
14 #include<algorithm>
15 #include<iomanip>
16 #include<vector>
17 #include<queue>
18 #include<stack>
19 #include<set>
20 #include<map>
21 #define read(n) n = read_n()
22 #define rep(i, n) for(int i=0;i!=n;++i)
23 #define per(i, n) for(int i=n-1;i>=0;--i)
24 #define Rep(i, sta, n) for(int i=sta;i!=n;++i)
25 #define rep1(i, n) for(int i=1;i<=n;++i)
26 #define per1(i, n) for(int i=n;i>=1;--i)
27 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
28 #define L k<<1
29 #define R k<<1|1
30 #define mid (tree[k].l+tree[k].r)>>1
31 #define eps 1e-10
32 using namespace std;
33 const int INF = 0x3f3f3f3f;
34 typedef long long ll;
35 
36 inline int read_n() {
37     char c=getchar();int x=0,f=1;
38     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
39     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
40     return x*f;
41 }
42 // -----------------------------------------------------
43 const int MAXN = 100+5;
44 const int MAXM = 4500+5;
45 
46 int n, m;
47 int dis[MAXN];
48 vector<int> a[MAXN], b[MAXN];
49 int vis[MAXN], ans;
50 
51 void dfs(vector<int> edge[MAXN], int x) {
52     vis[x] = 1;
53     ++ans;
54     if(!edge[x].size()) return;
55     for(int i = 0; i != edge[x].size(); ++i) {
56         if(!vis[edge[x][i]]) dfs(edge, edge[x][i]);
57     }
58 }
59 
60 int main() {
61     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
62     cin >> n >> m;
63     rep1(i, n) dis[i] = 0;
64     int x, y;
65     rep(i, m) {
66         cin >> x >> y;
67         a[x].push_back(y);
68         b[y].push_back(x);
69     }
70     int cnt = 0;
71     rep1(i, n) {
72         ans = 0;
73         rep1(j, n) vis[j] = 0;
74         dfs(a, i);
75         rep1(j, n) vis[j] = 0;
76         dfs(b, i);
77         if(ans == n+1) ++cnt;
78     }
79     cout << cnt << "
";
80     return 0;
81 }

View Code

// poj 2240

  1 /*
  2  * @Promlem: 
  3  * @Time Limit: ms
  4  * @Memory Limit: k
  5  * @Author: pupil-XJ
  6  * @Date: 2019-10-26 17:25:13
  7  * @LastEditTime: 2019-10-26 18:57:21
  8  */
  9 #include<cstdio>
 10 #include<cstring>
 11 #include<cmath>
 12 #include<iostream>
 13 #include<string>
 14 #include<algorithm>
 15 #include<iomanip>
 16 #include<vector>
 17 #include<queue>
 18 #include<stack>
 19 #include<set>
 20 #include<map>
 21 #define read(n) n = read_n()
 22 #define rep(i, n) for(int i=0;i!=n;++i)
 23 #define per(i, n) for(int i=n-1;i>=0;--i)
 24 #define Rep(i, sta, n) for(int i=sta;i!=n;++i)
 25 #define rep1(i, n) for(int i=1;i<=n;++i)
 26 #define per1(i, n) for(int i=n;i>=1;--i)
 27 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
 28 #define L k<<1
 29 #define R k<<1|1
 30 #define mid (tree[k].l+tree[k].r)>>1
 31 #define eps 1e-10
 32 using namespace std;
 33 const int INF = 0x3f3f3f3f;
 34 typedef long long ll;
 35 
 36 inline int read_n() {
 37     char c=getchar();int x=0,f=1;
 38     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 39     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 40     return x*f;
 41 }
 42 // -----------------------------------------------------
 43 const int MAXN = 30+5;
 44 typedef pair<int, double> Pair;
 45 
 46 int n, m;
 47 map<string, int> id;
 48 vector<Pair> edge[MAXN];
 49 
 50 int vis[MAXN], inq[MAXN];
 51 double dis[MAXN];
 52 
 53 bool SPFA() {
 54     dis[0] = 10.0;
 55     rep1(i, n) dis[i] = 0, inq[i] = vis[i] = 0;
 56     vis[0] = inq[0] = 1;
 57     queue<int> q;
 58     q.push(0);
 59     while(!q.empty()) {
 60         int u = q.front();
 61         q.pop();
 62         vis[u] = 0;
 63         rep(i, edge[u].size()) {
 64             Pair v = edge[u][i];
 65             if(dis[v.first] < dis[u]*v.second) {
 66                 dis[v.first] = dis[u]*v.second;
 67                 if(!vis[v.first]) {
 68                     vis[v.first] = 1;
 69                     q.push(v.first);
 70                     if(++inq[v.first] > n) return true;
 71                 }
 72             }
 73         }
 74     }
 75     return false;
 76 }
 77 
 78 int main() {
 79     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 80     int Case = 0;
 81     while(cin >> n && n) {
 82         Rep1(i, 0, n) edge[i].clear();
 83         int cnt = 1;
 84         string name;
 85         rep(i, n) {
 86             cin >> name;
 87             Pair p = make_pair(cnt, 10.0);
 88             edge[0].push_back(p);
 89             id[name] = cnt++;
 90         }
 91         cin >> m;
 92         string u, v;
 93         double r;
 94         rep(i, m) {
 95             cin >> u >> r >> v;
 96             Pair p = make_pair(id[v], r);
 97             edge[id[u]].push_back(p);
 98         }
 99         if(SPFA()) cout << "Case " << ++Case << ": Yes
";
100         else cout << "Case " << ++Case << ": No
";
101     }
102     return 0;
103 }

View Code

// poj 1511

  1 /*
  2  * @Promlem: 
  3  * @Time Limit: ms
  4  * @Memory Limit: k
  5  * @Author: pupil-XJ
  6  * @Date: 2019-10-27 00:31:47
  7  * @LastEditTime: 2019-10-27 01:10:54
  8  */
  9 #include<cstdio>
 10 #include<cstring>
 11 #include<cmath>
 12 #include<iostream>
 13 #include<string>
 14 #include<algorithm>
 15 #include<iomanip>
 16 #include<vector>
 17 #include<queue>
 18 #include<stack>
 19 #include<set>
 20 #include<map>
 21 #define read(n) n = read_n()
 22 #define rep(i, n) for(int i=0;i!=n;++i)
 23 #define per(i, n) for(int i=n-1;i>=0;--i)
 24 #define Rep(i, sta, n) for(int i=sta;i!=n;++i)
 25 #define rep1(i, n) for(int i=1;i<=n;++i)
 26 #define per1(i, n) for(int i=n;i>=1;--i)
 27 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
 28 #define L k<<1
 29 #define R k<<1|1
 30 #define mid (tree[k].l+tree[k].r)>>1
 31 #define eps 1e-10
 32 using namespace std;
 33 const int INF = 0x3f3f3f3f;
 34 typedef long long ll;
 35 
 36 inline int read_n() {
 37     char c=getchar();int x=0,f=1;
 38     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 39     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 40     return x*f;
 41 }
 42 // -----------------------------------------------------
 43 const int MAXN = 1000000+5;
 44 const int MAXM = 2000000+5;
 45 typedef pair<int, int> Pair;
 46 
 47 int n, m;
 48 ll sum;
 49 int s[MAXN], e[MAXN], v[MAXN];
 50 
 51 int num;
 52 struct node {
 53     int v, w, next;
 54 } edge[MAXM];
 55 
 56 int head[MAXN];
 57 inline void add(int x, int y, int w) {
 58     edge[num].v = y;
 59     edge[num].w = w;
 60     edge[num].next = head[x];
 61     head[x] = num++;
 62 }
 63 
 64 int dis[MAXN], vis[MAXN];
 65 
 66 void dij() {
 67     priority_queue<Pair, vector<Pair>, greater<Pair> > q;
 68     q.push(make_pair(0, 1));
 69     while(!q.empty()) {
 70         int u = q.top().second;
 71         q.pop();
 72         if(vis[u]) continue;
 73         vis[u] = 1;
 74         for(int i = head[u]; i != -1; i = edge[i].next) {
 75             if(!vis[edge[i].v] && dis[edge[i].v] > dis[u] + edge[i].w) {
 76                 dis[edge[i].v] = dis[u] + edge[i].w;
 77                 q.push(make_pair(dis[edge[i].v], edge[i].v));
 78             }
 79         }
 80     }
 81 }
 82 
 83 int main() {
 84     //ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 85     int T;
 86     scanf("%d", &T); //cin >> T;
 87     while(T--) {
 88         scanf("%d%d", &n, &m); //cin >> n >> m;
 89         int x, y, w;
 90         sum = 0;
 91         num = 1;
 92         rep1(i, n) head[i] = -1;
 93         rep(i, m) {
 94             scanf("%d%d%d", &s[i], &e[i], &v[i]); //cin >> s[i] >> e[i] >> v[i];
 95             add(s[i], e[i], v[i]);
 96         }
 97         rep1(i, n) {
 98             dis[i] = INF;
 99             vis[i] = 0;
100         }
101         dis[1] = 0;
102         dij();
103         rep1(i, n) {
104             sum += dis[i];
105             dis[i] = INF;
106             vis[i] = 0;
107             head[i] = -1;
108         }
109         dis[1] = 0;
110         num = 1;
111         rep(i, m) add(e[i], s[i], v[i]);
112         dij();
113         rep1(i, n) sum += dis[i];
114         printf("%lld
", sum); //cout << sum << "
";
115     }
116     return 0;
117 }

View Code

// poj 3159

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: ms
 4  * @Memory Limit: k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-10-27 15:10:27
 7  * @LastEditTime: 2019-10-27 16:10:46
 8  */
 9 #include<cstdio>
10 #include<cstring>
11 #include<cmath>
12 #include<iostream>
13 #include<string>
14 #include<algorithm>
15 #include<iomanip>
16 #include<vector>
17 #include<queue>
18 #include<stack>
19 #include<set>
20 #include<map>
21 #define read(n) n = read_n()
22 #define rep(i, n) for(int i=0;i!=n;++i)
23 #define per(i, n) for(int i=n-1;i>=0;--i)
24 #define Rep(i, sta, n) for(int i=sta;i!=n;++i)
25 #define rep1(i, n) for(int i=1;i<=n;++i)
26 #define per1(i, n) for(int i=n;i>=1;--i)
27 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
28 #define L k<<1
29 #define R k<<1|1
30 #define mid (tree[k].l+tree[k].r)>>1
31 #define eps 1e-10
32 using namespace std;
33 const int INF = 0x3f3f3f3f;
34 typedef long long ll;
35 
36 inline int read_n() {
37     char c=getchar();int x=0,f=1;
38     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
39     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
40     return x*f;
41 }
42 
43 const int MAXN = 30000+5;
44 const int MAXM = 150000+5;
45 
46 int num;
47 int head[MAXN];
48 struct node {// 链式向前星
49     int v, next;
50     int w;
51 } edge[MAXM];
52 
53 inline void add(int x, int y, int w) {
54     edge[num].v = y;
55     edge[num].next = head[x];
56     edge[num].w = w;
57     head[x] = num++;
58 }
59 
60 int n, m;
61 int dis[MAXN], vis[MAXN], inq[MAXN];
62 
63 bool SPFA(int s) {
64     stack<int> q;
65     dis[s] = 0;
66     vis[s] = inq[s] = 1;
67     q.push(s);
68     while(!q.empty()) {
69         int u = q.top();
70         q.pop();
71         vis[u] = 0;
72         for(int i = head[u]; i != -1; i = edge[i].next) {
73             int v = edge[i].v;
74             if(dis[v] > dis[u] + edge[i].w) {
75                 dis[v] = dis[u] + edge[i].w;
76                 if(!vis[v]) {
77                     q.push(v);
78                     vis[v] = 1;
79                     ++inq[v];
80                     if(inq[v] > n) return false;
81                 }
82             }
83         }
84     }
85     return true;
86 }
87 
88 int main() {
89     read(n); read(m); //cin >> n >> m;
90     int s, e, v;
91     num = 0;
92     for(int i = 1; i <= n; ++i) head[i] = -1, dis[i] = INF;
93     for(int i = 0; i != m; ++i) {
94         read(s); read(e); read(v); //cin >> s >> e >> v;
95         add(s, e, v);
96     }
97     if(SPFA(1)) cout << dis[n] << "
";
98     return 0;
99 }

View Code

// poj 2502

  1 /*
  2  * @Promlem: 
  3  * @Time Limit: ms
  4  * @Memory Limit: k
  5  * @Author: pupil-XJ
  6  * @Date: 2019-10-29 12:28:00
  7  * @LastEditTime: 2019-10-29 14:41:03
  8  */
  9 #include<cstdio>
 10 #include<cstring>
 11 #include<cmath>
 12 #include<iostream>
 13 #include<string>
 14 #include<algorithm>
 15 #include<iomanip>
 16 #include<vector>
 17 #include<queue>
 18 #include<stack>
 19 #include<set>
 20 #include<map>
 21 #define read(n) n = read_n()
 22 #define rep(i, n) for(int i=0;i!=n;++i)
 23 #define per(i, n) for(int i=n-1;i>=0;--i)
 24 #define Rep(i, sta, n) for(int i=sta;i!=n;++i)
 25 #define rep1(i, n) for(int i=1;i<=n;++i)
 26 #define per1(i, n) for(int i=n;i>=1;--i)
 27 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
 28 #define L k<<1
 29 #define R k<<1|1
 30 #define mid (tree[k].l+tree[k].r)>>1
 31 #define eps 1e-10
 32 using namespace std;
 33 const int INF = 0x3f3f3f3f;
 34 typedef long long ll;
 35 
 36 inline int read_n() {
 37     char c=getchar();int x=0,f=1;
 38     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 39     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 40     return x*f;
 41 }
 42 // -----------------------------------------------------
 43 #define walk 500.0/3.0
 44 #define car 2000.0/3.0
 45 const int MAXN = 202+5;
 46 const int MAXM = 200000+5;
 47 typedef pair<int,int> Pair;
 48 typedef pair<double,int> Pair2;
 49 
 50 int num;
 51 int head[MAXN];
 52 struct node {
 53     int v, next;
 54     double w;
 55 } edge[MAXM];
 56 
 57 inline void add(int x, int y, double w) {
 58     edge[num].v = y;
 59     edge[num].w = w;
 60     edge[num].next = head[x];
 61     head[x] = num++;
 62 }
 63 
 64 inline double get_dis(const Pair a, const Pair b) {
 65     int x1 = a.first, y1 = a.second;
 66     int x2 = b.first, y2 = b.second;
 67     return sqrt((double)((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
 68 }
 69 
 70 int cnt;
 71 Pair S, E;
 72 map<Pair,int> id;
 73 
 74 bool vis[MAXN];
 75 double dis[MAXN];
 76 
 77 double dij() {
 78     Rep1(i, 0, cnt) vis[i] = false, dis[i] = INF;
 79     dis[0] = 0.0;
 80     priority_queue<Pair2, vector<Pair2>, greater<Pair2> > q;
 81     q.push(make_pair(0.0, 0));
 82     while(!q.empty()) {
 83         int u = q.top().second;
 84         q.pop();
 85         if(vis[u]) continue;
 86         vis[u] = true;
 87         for(int i = head[u]; i != -1; i = edge[i].next) {
 88             int v = edge[i].v;
 89             if(dis[v] > dis[u] + edge[i].w) {
 90                 dis[v] = dis[u] + edge[i].w;
 91                 q.push(make_pair(dis[v], v));
 92             }
 93         }
 94     }
 95     return dis[1];
 96 }
 97 
 98 int main() {
 99     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
100     cin >> S.first >> S.second >> E.first >> E.second;
101     cnt = 2;
102     num = 0;
103     memset(head, -1, sizeof(head));
104     add(0, 1, get_dis(S, E)/(walk));
105     vector<Pair> line[100];
106     int p = 0, t = 0;
107     int x, y;
108     while(cin >> x >> y) {
109         if(x == -1) { ++p; t = 0; continue; }
110         Pair now = make_pair(x, y);
111         id[make_pair(p, t)] = cnt;
112         add(0, cnt, get_dis(S, now)/(walk));
113         add(cnt, 1, get_dis(E, now)/(walk));
114         if(t) {
115             for(int i = 0; i != t; ++i) {
116                 add(cnt, id[make_pair(p, i)], get_dis(line[p][i], now)/(walk));
117                 add(id[make_pair(p, i)], cnt, get_dis(line[p][i], now)/(walk));
118             }
119             add(cnt, cnt-1, get_dis(line[p][t-1], now)/(car));
120             add(cnt-1, cnt, get_dis(line[p][t-1], now)/(car));
121         }
122         for(int i = 0; i != p; ++i) {
123             for(int j = 0; j != line[i].size(); ++j) {
124                 add(cnt, id[make_pair(i, j)], get_dis(line[i][j], now)/(walk));
125                 add(id[make_pair(i, j)], cnt, get_dis(line[i][j], now)/(walk));
126             }
127         }
128         line[p].push_back(now);
129         ++t;
130         ++cnt;
131     }
132     cout << fixed << setprecision(0) << dij() << "
";
133     return 0;
134 }

View Code

// poj 1062

  1 /*
  2  * @Promlem: 
  3  * @Time Limit: ms
  4  * @Memory Limit: k
  5  * @Author: pupil-XJ
  6  * @Date: 2019-10-27 16:55:41
  7  * @LastEditTime: 2019-10-27 20:43:57
  8  */
  9 #include<cstdio>
 10 #include<cstring>
 11 #include<cmath>
 12 #include<iostream>
 13 #include<string>
 14 #include<algorithm>
 15 #include<iomanip>
 16 #include<vector>
 17 #include<queue>
 18 #include<stack>
 19 #include<set>
 20 #include<map>
 21 #define read(n) n = read_n()
 22 #define rep(i, n) for(int i=0;i!=n;++i)
 23 #define per(i, n) for(int i=n-1;i>=0;--i)
 24 #define Rep(i, sta, n) for(int i=sta;i!=n;++i)
 25 #define rep1(i, n) for(int i=1;i<=n;++i)
 26 #define per1(i, n) for(int i=n;i>=1;--i)
 27 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
 28 #define L k<<1
 29 #define R k<<1|1
 30 #define mid (tree[k].l+tree[k].r)>>1
 31 #define eps 1e-10
 32 using namespace std;
 33 const int INF = 0x3f3f3f3f;
 34 typedef long long ll;
 35 
 36 inline int read_n() {
 37     char c=getchar();int x=0,f=1;
 38     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 39     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 40     return x*f;
 41 }
 42 // -----------------------------------------------------
 43 const int MAXN = 100+5;
 44 const int MAXM = 10100+5;
 45 
 46 int num;
 47 int head[MAXN];
 48 struct node {
 49     int v, next;
 50     int w;
 51 } edge[MAXM];
 52 
 53 inline void add(int x, int y, int w) {
 54     edge[num].v = y;
 55     edge[num].next = head[x];
 56     edge[num].w = w;
 57     head[x] = num++;
 58 }
 59 
 60 int n, m, minn;
 61 int l, r;
 62 int value[MAXN], rank[MAXN];
 63 int vis[MAXN], dis[MAXN];
 64 
 65 int SPFA() {
 66     rep1(i, n) vis[i] = 0, dis[i] = value[1];
 67     dis[0] = 0;
 68     vis[0] = 1;
 69     stack<int> q;
 70     q.push(0);
 71     while(!q.empty()) {
 72         int u = q.top();
 73         q.pop();
 74         vis[u] = 0;
 75         for(int i = head[u]; i != -1; i = edge[i].next) {
 76             int v = edge[i].v;
 77             if(rank[v] >= l && rank[v] <= r && dis[v] > dis[u] + edge[i].w) {
 78                 dis[v] = dis[u] + edge[i].w;
 79                 if(!vis[v]) {
 80                     q.push(v);
 81                     vis[v] = 1;
 82                 }
 83             }
 84         }
 85     }
 86     return dis[1];
 87 }
 88 
 89 int main() {
 90     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 91     while(cin >> m >> n) {
 92         num = 0;
 93         Rep1(i, 0, n) head[i] = -1;
 94         int nm, e, w;
 95         rep1(i, n) {
 96             cin >> value[i] >> rank[i] >> nm;
 97             add(0, i, value[i]);
 98             rep(j, nm) {
 99                 cin >> e >> w;
100                 add(e, i, w);
101             }
102         }
103         minn = value[1];
104         Rep1(i, rank[1]-m, rank[1]) {
105             l = i; r = i + m;
106             int t = SPFA();
107             minn = min(minn, t);
108         }
109         cout << minn << "
";
110     }
111     return 0;
112 }

View Code

// poj 1847

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: ms
 4  * @Memory Limit: k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-10-29 11:37:17
 7  * @LastEditTime: 2019-10-29 11:55:54
 8  */
 9 #include<cstdio>
10 #include<cstring>
11 #include<cmath>
12 #include<iostream>
13 #include<string>
14 #include<algorithm>
15 #include<iomanip>
16 #include<vector>
17 #include<queue>
18 #include<stack>
19 #include<set>
20 #include<map>
21 #define read(n) n = read_n()
22 #define rep(i, n) for(int i=0;i!=n;++i)
23 #define per(i, n) for(int i=n-1;i>=0;--i)
24 #define Rep(i, sta, n) for(int i=sta;i!=n;++i)
25 #define rep1(i, n) for(int i=1;i<=n;++i)
26 #define per1(i, n) for(int i=n;i>=1;--i)
27 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
28 #define L k<<1
29 #define R k<<1|1
30 #define mid (tree[k].l+tree[k].r)>>1
31 #define eps 1e-10
32 using namespace std;
33 const int INF = 0x3f3f3f3f;
34 typedef long long ll;
35 
36 inline int read_n() {
37     char c=getchar();int x=0,f=1;
38     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
39     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
40     return x*f;
41 }
42 // -----------------------------------------------------
43 const int MAXN = 100+5;
44 const int MAXM = 10000+5;
45 typedef pair<int, int> Pair;
46 
47 int num;
48 int head[MAXN];
49 struct node {
50     int v, next, w;
51 } edge[MAXM];
52 
53 inline void add(int x, int y, int w) {
54     edge[num].v = y;
55     edge[num].next = head[x];
56     edge[num].w = w;
57     head[x] = num++;
58 }
59 
60 int n, S, E;
61 int vis[MAXN], dis[MAXN];
62 
63 int dij() {
64     priority_queue<Pair, vector<Pair>, greater<Pair> > q;
65     dis[S] = 0;
66     q.push(make_pair(0, S));
67     while(!q.empty()) {
68         int u = q.top().second;
69         q.pop();
70         if(vis[u]) continue;
71         vis[u] = 1;
72         for(int i = head[u]; i != -1; i = edge[i].next) {
73             int v = edge[i].v;
74             if(dis[v] > dis[u] + edge[i].w) {
75                 dis[v] = dis[u] + edge[i].w;
76                 q.push(make_pair(dis[v], v));
77             }
78         }
79     }
80     return dis[E] == INF ? -1 : dis[E];
81 }
82 
83 int main() {
84     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
85     cin >> n >> S >> E;
86     rep1(i, n) head[i] = -1, vis[i] = 0, dis[i] = INF;
87     int nm, e;
88     rep1(i, n) {
89         cin >> nm;
90         rep(j, nm) {
91             cin >> e;
92             if(!j) add(i, e, 0);
93             else add(i, e, 1);
94         }
95     }
96     cout << dij() << "
";
97     return 0;
98 }

View Code

// LightOJ 1074

  1 /*
  2  * @Promlem: 
  3  * @Time Limit: ms
  4  * @Memory Limit: k
  5  * @Author: pupil-XJ
  6  * @Date: 2019-10-30 16:37:27
  7  * @LastEditTime: 2019-10-30 17:52:14
  8  */
  9 #include<cstdio>
 10 #include<cstring>
 11 #include<cmath>
 12 #include<fstream>
 13 #include<iostream>
 14 #include<string>
 15 #include<functional>
 16 #include<algorithm>
 17 #include<sstream>
 18 #include<iomanip>
 19 #include<vector>
 20 #include<queue>
 21 #include<stack>
 22 #include<set>
 23 #include<map>
 24 #define read(n) n = read_n()
 25 #define rep(i, n) for(int i=0;i!=n;++i)
 26 #define per(i, n) for(int i=n-1;i>=0;--i)
 27 #define Rep(i, sta, n) for(int i=sta;i!=n;++i)
 28 #define rep1(i, n) for(int i=1;i<=n;++i)
 29 #define per1(i, n) for(int i=n;i>=1;--i)
 30 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
 31 #define L k<<1
 32 #define R k<<1|1
 33 #define mid (tree[k].l+tree[k].r)>>1
 34 #define eps 1e-10
 35 using namespace std;
 36 const int INF = 0x3f3f3f3f;
 37 typedef long long ll;
 38 
 39 inline int read_n() {
 40     char c=getchar();int x=0,f=1;
 41     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 42     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 43     return x*f;
 44 }
 45 // -----------------------------------------------------
 46 const int MAXN = 10000+5;
 47 const int MAXM = 1000000+5;
 48 
 49 struct node {
 50     int v, next, w;
 51 } edge[MAXM];
 52 
 53 int num;
 54 int head[MAXN];
 55 inline void add(int x, int y, int w) {
 56     edge[num].v = y;
 57     edge[num].w = w;
 58     edge[num].next = head[x];
 59     head[x] = num++;
 60 }
 61 
 62 int n, m, nm;
 63 int h[MAXN];
 64 
 65 inline int get_dis(int x, int y) {
 66     return (y-x)*(y-x)*(y-x);
 67 }
 68 
 69 int vis[MAXN], inq[MAXN], dis[MAXN];
 70 void SPFA() {
 71     dis[1] = 0;
 72     vis[1] = inq[1] = 1;
 73     queue<int> st;
 74     st.push(1);
 75     while(!st.empty()) {
 76         int u = st.front();
 77         st.pop();
 78         vis[u] = 0;
 79         for(int i = head[u]; i != -1; i = edge[i].next) {
 80             int v = edge[i].v;
 81             if(dis[v] > dis[u] + edge[i].w) {
 82                 dis[v] = dis[u] + edge[i].w;
 83                 if(!vis[v] && inq[v] <= n) {
 84                     vis[v] = 1;
 85                     st.push(v);
 86                     ++inq[v];
 87                 }
 88             }
 89         }
 90     }
 91 }
 92 
 93 int main() {
 94     //ofstream outputfile;
 95     //outputfile.open("Putout.txt");
 96     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 97     int T, cnt = 1;
 98     cin >> T;
 99     while(T--) {
100         cin >> n;
101         num = 0;
102         rep1(i, n) cin >> h[i], vis[i] = inq[i] = 0, dis[i] = INF, head[i] = -1;
103         cin >> m;
104         int x, y;
105         rep(i, m) {
106             cin >> x >> y;
107             add(x, y, get_dis(h[x], h[y]));
108         }
109         cin >> nm;
110         cout << "Case " << cnt++ << ":
";
111         SPFA();
112         rep(i, nm) {
113             cin >> x;
114             if(dis[x] < 3 || dis[x] == INF) cout << "?
";
115             else cout << dis[x] << "
";
116         }
117     }
118     //outputfile.close();
119     return 0;
120 }

View Code

// hdu 4725

  1 /*
  2  * @Promlem: 
  3  * @Time Limit: ms
  4  * @Memory Limit: k
  5  * @Author: pupil-XJ
  6  * @Date: 2019-10-29 15:31:38
  7  * @LastEditTime: 2019-10-29 23:43:12
  8  */
  9 #include<cstdio>
 10 #include<cstring>
 11 #include<cmath>
 12 #include<iostream>
 13 #include<fstream>
 14 #include<sstream>
 15 #include<string>
 16 #include<algorithm>
 17 #include<functional>
 18 #include<iomanip>
 19 #include<vector>
 20 #include<queue>
 21 #include<stack>
 22 #include<set>
 23 #include<map>
 24 #define read(n) n = read_n()
 25 #define rep(i, n) for(int i=0;i!=n;++i)
 26 #define per(i, n) for(int i=n-1;i>=0;--i)
 27 #define Rep(i, sta, n) for(int i=sta;i!=n;++i)
 28 #define rep1(i, n) for(int i=1;i<=n;++i)
 29 #define per1(i, n) for(int i=n;i>=1;--i)
 30 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
 31 #define L k<<1
 32 #define R k<<1|1
 33 #define mid (tree[k].l+tree[k].r)>>1
 34 #define eps 1e-10
 35 using namespace std;
 36 const int INF = 0x3f3f3f3f;
 37 typedef long long ll;
 38 
 39 inline int read_n() {
 40     char c=getchar();int x=0,f=1;
 41     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 42     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 43     return x*f;
 44 }
 45 // -----------------------------------------------------
 46 const int MAXN = 200000+5;
 47 const int MAXM = MAXN*4;
 48 typedef pair<int,int> Pair;
 49 
 50 int num;
 51 int head[MAXN];
 52 struct node {
 53     int v, next, w;
 54 } edge[MAXM];
 55 
 56 inline void add(int x, int y, int w) {
 57     edge[num].v = y;
 58     edge[num].w = w;
 59     edge[num].next = head[x];
 60     head[x] = num++;
 61 }
 62 
 63 int n, m, c;
 64 int cnt;
 65 int p[MAXN];
 66 
 67 int dis[MAXN], vis[MAXN];
 68 inline int dij() {
 69     priority_queue<Pair, vector<Pair>, greater<Pair> > q;
 70     dis[1] = 0;
 71     q.push(make_pair(0, 1));
 72     while(!q.empty()) {
 73         int u = q.top().second;
 74         q.pop();
 75         if(vis[u]) continue;
 76         vis[u] = 1;
 77         if(u == n) break;
 78         for(int i = head[u]; i != -1; i = edge[i].next) {
 79             int v = edge[i].v;
 80             if(!vis[v] && dis[v] > dis[u] + edge[i].w) {
 81                 dis[v] = dis[u] + edge[i].w;
 82                 q.push(make_pair(dis[v], v));
 83             }
 84         }
 85     }
 86     return dis[n] == INF ? -1 : dis[n];
 87 }
 88 
 89 int main() {
 90     int T, Case = 1;
 91     read(T);
 92     while(T--) {
 93         read(n);read(m);read(c);
 94         num = 0;
 95         vector<int> layers[MAXN];
 96         int x, y, w;
 97         rep1(i, n) {
 98             read(x);
 99             layers[x].push_back(i);
100             head[i] = -1;
101             vis[i] = p[i] = 0;
102             dis[i] = INF;
103         }
104         cnt = n;
105         rep1(i, n) {
106             int nm = layers[i].size();
107             if(nm) p[i] = ++cnt;
108             else continue;
109             head[cnt] = -1;
110             vis[cnt] = 0;
111             dis[cnt] = INF;
112             rep(j, nm) {
113                 add(layers[i][j], p[i], 0);
114                 if(i != 1 && p[i-1]) add(p[i-1], layers[i][j], c);
115             }
116             if(i == 1) continue;
117             nm = layers[i-1].size();
118             rep(j, nm) add(p[i], layers[i-1][j], c);
119         }
120         rep(i, m) {
121             read(x);read(y);read(w);
122             add(x, y, w);
123             add(y, x, w);
124         }
125         printf("Case #%d: %d
", Case++, dij());
126     }
127     return 0;
128 }

View Code

// poj 4370

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: ms
 4  * @Memory Limit: k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-10-30 16:14:50
 7  * @LastEditTime: 2019-10-30 16:29:27
 8  */
 9 #include<cstdio>
10 #include<cstring>
11 #include<cmath>
12 #include<iostream>
13 #include<string>
14 #include<functional>
15 #include<algorithm>
16 #include<sstream>
17 #include<iomanip>
18 #include<vector>
19 #include<queue>
20 #include<stack>
21 #include<set>
22 #include<map>
23 #define read(n) n = read_n()
24 #define rep(i, n) for(int i=0;i!=n;++i)
25 #define per(i, n) for(int i=n-1;i>=0;--i)
26 #define Rep(i, sta, n) for(int i=sta;i!=n;++i)
27 #define rep1(i, n) for(int i=1;i<=n;++i)
28 #define per1(i, n) for(int i=n;i>=1;--i)
29 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
30 #define L k<<1
31 #define R k<<1|1
32 #define mid (tree[k].l+tree[k].r)>>1
33 #define eps 1e-10
34 using namespace std;
35 const int INF = 0x3f3f3f3f;
36 typedef long long ll;
37 
38 inline int read_n() {
39     char c=getchar();int x=0,f=1;
40     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
41     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
42     return x*f;
43 }
44 // -----------------------------------------------------
45 const int MAXN = 300+5;
46 
47 int n;
48 int G[MAXN][MAXN];
49 
50 int vis[MAXN], dis[MAXN];
51 void SPFA(int s) {
52     stack<int> st;
53     rep1(i, n) {
54         if(i == s) dis[i] = INF, vis[i] = 0;
55         else dis[i] = G[s][i], vis[i] = 1, st.push(i);
56     }
57     while(!st.empty()) {
58         int u = st.top();
59         st.pop();
60         vis[u] = 0;
61         rep1(i, n) {
62             if(dis[i] > dis[u] + G[u][i]) {
63                 dis[i] = dis[u] + G[u][i];
64                 if(!vis[i]) st.push(i), vis[i] = 1;
65             }
66         }
67     }
68 }
69 
70 int main() {
71     while(scanf("%d", &n) == 1) {
72         rep1(i, n) rep1(j, n) scanf("%d", &G[i][j]); //cin >> G[i][j];
73         int path, s1, s2;
74         SPFA(1); path = dis[n]; s1 = dis[1];
75         SPFA(n); s2 = dis[n];
76         printf("%d
", min(path, s1+s2)); //cout << min(path, s1+s2) << "
";
77     }
78     return 0;
79 }

View Code

// poj 3169

  1 /*
  2  * @Promlem: 
  3  * @Time Limit: ms
  4  * @Memory Limit: k
  5  * @Author: pupil-XJ
  6  * @Date: 2019-10-30 01:24:23
  7  * @LastEditTime: 2019-10-30 01:38:28
  8  */
  9 #include<cstdio>
 10 #include<cstring>
 11 #include<cmath>
 12 #include<iostream>
 13 #include<string>
 14 #include<functional>
 15 #include<algorithm>
 16 #include<sstream>
 17 #include<iomanip>
 18 #include<vector>
 19 #include<queue>
 20 #include<stack>
 21 #include<set>
 22 #include<map>
 23 #define read(n) n = read_n()
 24 #define rep(i, n) for(int i=0;i!=n;++i)
 25 #define per(i, n) for(int i=n-1;i>=0;--i)
 26 #define Rep(i, sta, n) for(int i=sta;i!=n;++i)
 27 #define rep1(i, n) for(int i=1;i<=n;++i)
 28 #define per1(i, n) for(int i=n;i>=1;--i)
 29 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
 30 #define L k<<1
 31 #define R k<<1|1
 32 #define mid (tree[k].l+tree[k].r)>>1
 33 #define eps 1e-10
 34 using namespace std;
 35 const int INF = 0x3f3f3f3f;
 36 typedef long long ll;
 37 
 38 inline int read_n() {
 39     char c=getchar();int x=0,f=1;
 40     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 41     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 42     return x*f;
 43 }
 44 // -----------------------------------------------------
 45 const int MAXN = 1000+5;
 46 const int MAXM = 20000+5;
 47 
 48 int num;
 49 int head[MAXN];
 50 struct node {
 51     int v, next, w;
 52 } edge[MAXM];
 53 
 54 inline void add(int x, int y, int w) {
 55     edge[num].v = y;
 56     edge[num].w = w;
 57     edge[num].next = head[x];
 58     head[x] = num++;
 59 }
 60 
 61 int n, m1, m2;
 62 
 63 int vis[MAXN], inq[MAXN], dis[MAXN];
 64 bool SPFA() {
 65     rep1(i, n) vis[i] = inq[i] = 0, dis[i] = INF;
 66     vis[1] = inq[1] = 1;
 67     dis[1] = 0;
 68     stack<int> st;
 69     st.push(1);
 70     while(!st.empty()) {
 71         int u = st.top();
 72         st.pop();
 73         vis[u] = 0;
 74         for(int i = head[u]; i != -1; i = edge[i].next) {
 75             int v = edge[i].v;
 76             if(dis[v] > dis[u] + edge[i].w) {
 77                 dis[v] = dis[u] + edge[i].w;
 78                 if(!vis[v]) {
 79                     vis[v] = 1;
 80                     st.push(v);
 81                     if(++inq[v] > n) return false;
 82                 }
 83             }
 84         }
 85     }
 86     return true;
 87 }
 88 
 89 int main() {
 90     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 91     cin >> n >> m1 >> m2;
 92     num = 0;
 93     rep1(i, n) head[i] = -1;
 94     int x, y, w;
 95     rep(i, m1) {
 96         cin >> x >> y >> w;
 97         add(x, y, w);
 98     }
 99     rep(i, m2) {
100         cin >> x >> y >> w;
101         add(y, x, -w);
102     }
103     if(!SPFA()) cout << "-1
";
104     else if(dis[n] == INF) cout << "-2
";
105     else cout << dis[n] << endl; 
106     return 0;
107 }

View Code