「题解」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(传递闭包 floyd 或 DFS)
  • POJ-2240 Arbitrage(判断正环)
  • POJ-1511 Invitation Cards(求往返最短路,反向连边)
  • POJ-1847 Tram(水)
  • POJ-1062 昂贵的聘礼*
  • POJ-3159 Candies(伪差分约束系统(裸最短路)+ 输入输出挂)
  • POJ-2502 Subway(建图麻烦)
  • POJ-3169 Layout(差分约束系统,输出差值)
  • LightOJ-1074 Extended Traffic(判断所有负环)
  • HDU-4725 The Shortest Path in Nya Graph(建图技巧)
  • HDU-3416 Marriage Match IV(最短路 + 最大流 找出最短路经过的边)

代码最后附简单题解

模板

Dijkstra_simple

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
* 单源最短路径,Dijkstra 算法,邻接矩阵形式,复杂度为O(n^2)
* 求出源 beg 到所有点的最短路径,传入图的顶点数,和邻接矩阵 cost[][]
* 返回各点的最短路径 lowcost[], 路径 pre[].pre[i] 记录 beg 到 i
* 路径上的父结点,pre[beg]=-1
* 可更改路径权类型,但是权值必须为非负
*/

const int MAXN = 1010;
#define typec int
const typec INF = 0x3f3f3f3f;
bool vis[MAXN];
int pre[MAXN];
void Dijkstra(typec cost[][MAXN], typec lowcost[], int n, int beg) {
for (int i = 0; i < n; i++) {
lowcost[i] = INF;
vis[i] = false;
pre[i] = -1;
}
lowcost[beg] = 0;
for (int j = 0; j < n; j++) {
int k = -1;
int Min = INF;
for (int i = 0; i < n; i++) {
if (!vis[i] && lowcost[i] < Min) {
Min = lowcost[i];
k = i;
}
}
if (k == -1) break;
vis[k] = true;
for (int i = 0; i < n; i++) {
if (!vis[i] && lowcost[k] + cost[k][i] < lowcost[i]) {
lowcost[i] = lowcost[k] + cost[k][i];
pre[i] = k;
}
}
}
}

Dijkstra_set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/* * 使用优先队列优化 Dijkstra 算法
* 复杂度 O(ElogE)
* 注意对
* vector<Edge>E[MAXN] 进行初始化后加边
*/

#include <string.h>
#include <queue>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1000010;

struct qnode {
int v, c;
qnode(int _v = 0, int _c = 0) : v(_v), c(_c){};
bool operator<(const qnode &r) const { return c > r.c; }
};

struct Edge {
int v, cost;
Edge(int _v = 0, int _cost = 0) : v(_v), cost(_cost) {}
};
vector<Edge> E[MAXN];
bool vis[MAXN];
int dist[MAXN];

//点的编号从 1 开始

void Dijkstra(int n, int start) {
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) dist[i] = INF;
priority_queue<qnode> que;
while (!que.empty()) que.pop();
dist[start] = 0;
que.push(qnode(start, 0));
qnode tmp;
while (!que.empty()) {
tmp = que.top();
que.pop();
int u = tmp.v;
if (vis[u]) continue;
vis[u] = true;
for (int i = 0; i < E[u].size(); i++) {
int v = E[tmp.v][i].v;
int cost = E[u][i].cost;
if (!vis[v] && dist[v] > dist[u] + cost) {
dist[v] = dist[u] + cost;
que.push(qnode(v, dist[v]));
}
}
}
}
void addedge(int u, int v, int w) { E[u].push_back(Edge(v, w)); }

Bellman_Ford

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*
* 单源最短路 bellman_ford 算法,复杂度 O(VE)
* 可以处理负边权图。
* 可以判断是否存在负环回路。返回 true, 当且仅当图中不包含从源点可达的负权回路
* vector<Edge>E; 先 E.clear() 初始化,然后加入所有边
* 点的编号从 1 开始 (从 0 开始简单修改就可以了)
*/
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 550;

int dist[MAXN];

struct Edge {
int u, v;
int cost;
Edge(int _u = 0, int _v = 0, int _cost = 0) : u(_u), v(_v), cost(_cost) {}
};
vector<Edge> E;
//点的编号从 1 开始
bool bellman_ford(int start, int n) {
for (int i = 1; i <= n; i++) dist[i] = INF;
dist[start] = 0;
//最多做 n-1 次
for (int i = 1; i < n; i++) {
bool flag = false;
for (int j = 0; j < E.size(); j++) {
int u = E[j].u;
int v = E[j].v;
int cost = E[j].cost;
if (dist[v] > dist[u] + cost) {
dist[v] = dist[u] + cost;
flag = true;
}
if (!flag) return true;
}
}
for (int j = 0; j < E.size(); j++) {
if (dist[E[j].v] > dist[E[j].u] + E[j].cost) {
return false;
}
}
return true;
}

SPFA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/*
* 单源最短路 SPFA
* 时间复杂度 0(kE)
* 这个是队列实现,有时候改成栈实现会更加快,很容易修改
* 这个复杂度是不定的
*/

#include <queue>
#include <vector>
using namespace std;

const int MAXN = 1010;
const int INF = 0x3f3f3f3f;
struct Edge {
int v;
int cost;
Edge(int _v = 0, int _cost = 0) : v(_v), cost(_cost) {}
};
vector<Edge> E[MAXN];
void addedge(int u, int v, int w) { E[u].push_back(Edge(v, w)); }
bool vis[MAXN]; //在队列标志
int cnt[MAXN]; //每个点的入队列次数
int dist[MAXN];

bool SPFA(int start, int n) {
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) dist[i] = INF;
vis[start] = true;
dist[start] = 0;
queue<int> que;
que.push(start);
memset(cnt, 0, sizeof(cnt));
cnt[start] = 1;
while (!que.empty()) {
int u = que.front();
que.pop();
vis[u] = false;
for (int i = 0; i < E[u].size(); i++) {
int v = E[u][i].v;
if (dist[v] > dist[u] + E[u][i].cost) {
dist[v] = dist[u] + E[u][i].cost;
if (!vis[v]) {
vis[v] = true;
que.push(v);
if (++cnt[v] > n) return false;
// cnt[i] 为入队列次数,用来判定是否存在负环回路
}
}
}
}
return true;
}

Floyd

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <algorithm>
using namespace std;
const int MAXN = 105;
int dist[MAXN][MAXN];
void floyd(int n) {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[j][k]);
}
}
}
}

输入输出挂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>

int Scan() { //输入外挂
int res = 0, flag = 0;
char ch;
if ((ch = getchar()) == '-')
flag = 1;
else if (ch >= '0' && ch <= '9')
res = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') res = res * 10 + (ch - '0');
return flag ? -res : res;
}

void Out(int a) { //输出外挂
if (a < 0) {
putchar('-');
a = -a;
}
if (a >= 10) Out(a / 10);
putchar(a % 10 + '0');
}

代码

POJ-2387 Til the Cows Come Home

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// POJ-2387 Til the Cows Come Home
// https://vjudge.net/problem/POJ-2387

#include <string.h>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1000010;

struct qnode {
int v, c;
qnode(int _v = 0, int _c = 0) : v(_v), c(_c){};
bool operator<(const qnode &r) const { return c > r.c; }
};

struct Edge {
int v, cost;
Edge(int _v = 0, int _cost = 0) : v(_v), cost(_cost) {}
};
vector<Edge> E[MAXN];
bool vis[MAXN];
int dist[MAXN];

//点的编号从 1 开始

void Dijkstra(int n, int start) {
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) dist[i] = INF;
priority_queue<qnode> que;
while (!que.empty()) que.pop();
dist[start] = 0;
que.push(qnode(start, 0));
qnode tmp;
while (!que.empty()) {
tmp = que.top();
que.pop();
int u = tmp.v;
if (vis[u]) continue;
vis[u] = true;
for (int i = 0; i < E[u].size(); i++) {
int v = E[tmp.v][i].v;
int cost = E[u][i].cost;
if (!vis[v] && dist[v] > dist[u] + cost) {
dist[v] = dist[u] + cost;
que.push(qnode(v, dist[v]));
}
}
}
}
void addedge(int u, int v, int w) { E[u].push_back(Edge(v, w)); }

int main() {
int T, N;
while (~scanf("%d%d", &T, &N)) {
for (int i = 0; i < MAXN; i++) {
E[i].clear();
}
for (int i = 0; i < T; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
addedge(u, v, w);
addedge(v, u, w);
}
Dijkstra(N, 1);
printf("%d\n", dist[N]);
}
}

// 裸的 dji_set,坑:多组输入!

POJ-2253 Frogger

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// POJ-2253 Frogger
// https://vjudge.net/problem/POJ-2253

#include <string.h>
#include <cmath>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1000010;

struct qnode {
int v;
double c;
qnode(int _v = 0, double _c = 0) : v(_v), c(_c){};
bool operator<(const qnode &r) const { return c > r.c; }
};

struct Edge {
int v;
double cost;
Edge(int _v = 0, double _cost = 0) : v(_v), cost(_cost) {}
};
vector<Edge> E[MAXN];
bool vis[MAXN];
double dist[MAXN];

//点的编号从 1 开始

void Dijkstra(int n, int start) {
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) dist[i] = INF;
priority_queue<qnode> que;
while (!que.empty()) que.pop();
dist[start] = 0;
que.push(qnode(start, 0));
qnode tmp;
while (!que.empty()) {
tmp = que.top();
que.pop();
int u = tmp.v;
if (vis[u]) continue;
vis[u] = true;
for (int i = 0; i < E[u].size(); i++) {
int v = E[tmp.v][i].v;
double cost = E[u][i].cost;
if (!vis[v] && dist[v] > max(dist[u], cost)) {
dist[v] = max(dist[u], cost);
que.push(qnode(v, dist[v]));
}
}
}
}
void addedge(int u, int v, double w) { E[u].push_back(Edge(v, w)); }

double tone_x[MAXN], tone_y[MAXN];

double len(int a, int b) {
return sqrt((tone_x[a] - tone_x[b]) * (tone_x[a] - tone_x[b]) +
(tone_y[a] - tone_y[b]) * (tone_y[a] - tone_y[b]));
}

int main() {
int N;
int CNT = 1;
while (~scanf("%d", &N)) {
if (N == 0) break;
for (int i = 0; i < MAXN; i++) {
E[i].clear();
}
for (int i = 1; i <= N; i++) {
scanf("%lf%lf", &tone_x[i], &tone_y[i]);
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i == j) continue;
addedge(i, j, len(i, j));
}
}
Dijkstra(N, 1);
printf("Scenario #%d\n", CNT++);
printf("Frog Distance = %.3lf\n\n", dist[2]);
}
}

// 最短路变形,大坑:POJ选择C++才能过???

POJ-1797 Heavy Transportation

dij_set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// POJ-1797 Heavy Transportation
// https://vjudge.net/problem/POJ-1797

#include <string.h>
#include <queue>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 10000;

struct qnode {
int v, c;
qnode(int _v = 0, int _c = 0) : v(_v), c(_c){};
bool operator<(const qnode &r) const { return c < r.c; }
};

struct Edge {
int v, cost;
Edge(int _v = 0, int _cost = 0) : v(_v), cost(_cost) {}
};
vector<Edge> E[MAXN];
bool vis[MAXN];
int dist[MAXN];

//点的编号从 1 开始

void Dijkstra(int n, int start) {
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) dist[i] = 0;
priority_queue<qnode> que;
while (!que.empty()) que.pop();
dist[start] = INF;
que.push(qnode(start, dist[start]));
qnode tmp;
while (!que.empty()) {
tmp = que.top();
que.pop();
int u = tmp.v;
if (vis[u]) continue;
vis[u] = true;
for (int i = 0; i < E[u].size(); i++) {
int v = E[tmp.v][i].v;
int cost = E[u][i].cost;
if (!vis[v] && dist[v] < min(dist[u], cost)) {
dist[v] = min(dist[u], cost);
que.push(qnode(v, dist[v]));
}
}
}
}
void addedge(int u, int v, int w) { E[u].push_back(Edge(v, w)); }
int main() {
int T, CNT = 1;
scanf("%d", &T);
while (CNT <= T) {
for (int i = 0; i < MAXN; i++) {
E[i].clear();
}
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
addedge(a, b, w);
addedge(b, a, w);
}
Dijkstra(n, 1);
printf("Scenario #%d:\n%d\n\n", CNT++, dist[n]);
}
return 0;
}

//求 1 - n 中所有路径中最大边权的最小值

dij_simple

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// POJ-1797 Heavy Transportation
// https://vjudge.net/problem/POJ-1797

#include <string.h>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 1010;
#define typec int
const typec INF = 0x3f3f3f3f;

int xcost[MAXN][MAXN];
int dist[MAXN];
bool vis[MAXN];
void Dijkstra(typec cost[][MAXN], typec lowcost[], int n, int beg) {
for (int i = 0; i < n; i++) {
lowcost[i] = 0;
vis[i] = false;
}
lowcost[beg] = INF;
for (int j = 0; j < n; j++) {
int k = -1;
int Min = 0;
for (int i = 0; i < n; i++) {
if (!vis[i] && lowcost[i] > Min) {
Min = lowcost[i];
k = i;
}
}
if (k == -1) break;
vis[k] = true;
for (int i = 0; i < n; i++) {
if (!vis[i] && min(lowcost[k], cost[k][i]) > lowcost[i]) {
lowcost[i] = min(lowcost[k], cost[k][i]);
}
}
}
}

int main() {
int T, CNT = 1;
scanf("%d", &T);
while (CNT <= T) {
memset(xcost, 0, sizeof(xcost));
memset(dist, 0, sizeof(dist));

int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
a--;
b--;
xcost[a][b] = xcost[b][a] = max(w, xcost[a][b]);
}
Dijkstra(xcost, dist, n, 0);
printf("Scenario #%d:\n%d\n\n", CNT++, dist[n - 1]);
}
return 0;
}

//求 1 - n 中所有路径中最大边权的最小值

Kruskal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// POJ-1797 Heavy Transportation
// https://vjudge.net/problem/POJ-1797

#include <string.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;

const int MAXN = 2005; //最大点数
const int MAXM = 2000005; //最大边数
int F[MAXN];
struct Edge {
int u, v, w;
} edge[MAXM]; //存储边的信息,包括起点/终点/权值

int tol; //边数,加边前赋值为 0

void addedge(int u, int v, int w) {
edge[tol].u = u;
edge[tol].v = v;
edge[tol++].w = w;
}

// 排序函数,讲边按照权值从大到小排序
bool cmp(Edge a, Edge b) { return a.w > b.w; }

int find(int x) {
if (F[x] == -1)
return x;
else
return F[x] = find(F[x]);
}
int xans;
// 传入点数,返回最小生成树的权值,如果不连通返回 -1
int Kruskal(int n) {
memset(F, -1, sizeof(F));
sort(edge, edge + tol, cmp);
int cnt = 0; //计算加入的边数
int ans = 0;
for (int i = 0; i < tol; i++) {
int u = edge[i].u;
int v = edge[i].v;
int w = edge[i].w;
int t1 = find(u);
int t2 = find(v);
if (t1 != t2) {
ans += w;
xans = min(xans, w);
F[t1] = t2;
cnt++;
}

//----------------------------------------------------------------
int x1 = find(1);
int xn = find(n);
if (x1 == xn) break;
//----------------------------------------------------------------
// 1-n连接后就不需贪心

if (cnt == n - 1) break;
}
if (cnt < n - 1) return -1; //不连通
return ans;
}

int main() {
int T, CNT = 1;
scanf("%d", &T);
while (CNT <= T) {
tol = 0;
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
addedge(a, b, w);
// addedge(b, a, w);
}
xans = 0x3f3f3f3f;
Kruskal(n);
printf("Scenario #%d:\n%d\n\n", CNT++, xans);
}
return 0;
}

//求 1 - n 中所有路径中最大边权的最小值

POJ-3268 Silver Cow Party

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// POJ-3268 Silver Cow Party
// https://vjudge.net/problem/POJ-3268

#include <string.h>
#include <queue>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 10000;

struct qnode {
int v, c;
qnode(int _v = 0, int _c = 0) : v(_v), c(_c){};
bool operator<(const qnode &r) const { return c > r.c; }
};

struct Edge {
int u, v, cost;
Edge(int _u = 0, int _v = 0, int _cost = 0) : u(_u), v(_v), cost(_cost) {}
};
vector<Edge> E[MAXN];
vector<Edge> Etmp;

bool vis[MAXN];
int dist[MAXN];
int tdist[MAXN];
//点的编号从 1 开始

void Dijkstra(int n, int start) {
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) dist[i] = INF;
priority_queue<qnode> que;
while (!que.empty()) que.pop();
dist[start] = 0;
que.push(qnode(start, 0));
qnode tmp;
while (!que.empty()) {
tmp = que.top();
que.pop();
int u = tmp.v;
if (vis[u]) continue;
vis[u] = true;
for (int i = 0; i < E[u].size(); i++) {
int v = E[tmp.v][i].v;
int cost = E[u][i].cost;
if (!vis[v] && dist[v] > dist[u] + cost) {
dist[v] = dist[u] + cost;
que.push(qnode(v, dist[v]));
}
}
}
}
void addedge(int u, int v, int w) { E[u].push_back(Edge(u, v, w)); }

int main() {
int n, m, x;
scanf("%d%d%d", &n, &m, &x);
for (int i = 0; i < m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
addedge(a, b, c);
Etmp.push_back(Edge(a, b, c));
}
Dijkstra(n, x);
for (int i = 1; i <= n; i++) {
tdist[i] = dist[i];
E[i].clear();
}
for (int i = 0; i < m; i++) {
addedge(Etmp[i].v, Etmp[i].u, Etmp[i].cost);
}
int ans = 0;
Dijkstra(n, x);
for (int i = 1; i <= n; i++) {
tdist[i] += dist[i];
ans = max(ans, tdist[i]);
}
printf("%d\n", ans);

return 0;
}

// 从 x 向所有点跑一次 dij,将边反向再来一次,求往返距离

POJ-1860 Currency Exchange

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// POJ-1860 Currency Exchange
// https://vjudge.net/problem/POJ-1860

#include <queue>
#include <vector>
using namespace std;

int N, M, S;
double V;

const int MAXN = 1010;
const int INF = 10000;
struct Edge {
int v;
double cost;
double c;
Edge(int _v = 0, double _cost = 0, double _c = 0)
: v(_v), cost(_cost), c(_c) {}
};
vector<Edge> E[MAXN];
void addedge(int u, int v, double w, double c) {
E[u].push_back(Edge(v, w, c));
}
bool vis[MAXN]; //在队列标志
int cnt[MAXN]; //每个点的入队列次数
double dist[MAXN];

bool SPFA(int start, int n) {
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) dist[i] = 0;
vis[start] = true;
dist[start] = V;
queue<int> que;
que.push(start);
memset(cnt, 0, sizeof(cnt));
cnt[start] = 1;
while (!que.empty()) {
int u = que.front();
que.pop();
vis[u] = false;
for (int i = 0; i < E[u].size(); i++) {
int v = E[u][i].v;
if (dist[v] < (dist[u] - E[u][i].c) * E[u][i].cost) {
dist[v] = (dist[u] - E[u][i].c) * E[u][i].cost;
if (!vis[v]) {
vis[v] = true;
que.push(v);
if (++cnt[v] > n) return true;
// cnt[i] 为入队列次数,用来判定是否存在负环回路
}
}
}
}
return false;
}

int main() {
scanf("%d%d%d%lf", &N, &M, &S, &V);
for (int i = 0; i < M; i++) {
int a, b;
double rab, cab, rba, cba;
scanf("%d%d%lf%lf%lf%lf", &a, &b, &rab, &cab, &rba, &cba);
addedge(a, b, rab, cab);
addedge(b, a, rba, cba);
}

if (SPFA(S, N)) {
printf("YES");
} else {
printf("NO");
}
printf("\n");

return 0;
}

// 换汇问题,最长路判断正环

POJ-3259 Wormholes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// POJ-3159 Candies
// https://vjudge.net/problem/POJ-3159

#include <string.h>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

int Scan() { //输入外挂
int res = 0, flag = 0;
char ch;
if ((ch = getchar()) == '-')
flag = 1;
else if (ch >= '0' && ch <= '9')
res = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') res = res * 10 + (ch - '0');
return flag ? -res : res;
}

void Out(int a) { //输出外挂
if (a < 0) {
putchar('-');
a = -a;
}
if (a >= 10) Out(a / 10);
putchar(a % 10 + '0');
}
const int INF = 0x3f3f3f3f;
const int MAXN = 30005;

struct qnode {
int v, c;
qnode(int _v = 0, int _c = 0) : v(_v), c(_c){};
bool operator<(const qnode &r) const { return c > r.c; }
};

struct Edge {
int v, cost;
Edge(int _v = 0, int _cost = 0) : v(_v), cost(_cost) {}
};
vector<Edge> E[MAXN];
bool vis[MAXN];
int dist[MAXN];

//点的编号从 1 开始

void Dijkstra(int n, int start) {
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) dist[i] = INF;
priority_queue<qnode> que;
while (!que.empty()) que.pop();
dist[start] = 0;
que.push(qnode(start, 0));
qnode tmp;
while (!que.empty()) {
tmp = que.top();
que.pop();
int u = tmp.v;
if (vis[u]) continue;
vis[u] = true;
for (int i = 0; i < E[u].size(); i++) {
int v = E[tmp.v][i].v;
int cost = E[u][i].cost;
if (!vis[v] && dist[v] > dist[u] + cost) {
dist[v] = dist[u] + cost;
que.push(qnode(v, dist[v]));
}
}
}
}
void addedge(int u, int v, int w) { E[u].push_back(Edge(v, w)); }
int main() {
int n, m;
n = Scan();
m = Scan();
// scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
int a, b, c;
a = Scan();
b = Scan();
c = Scan();
// scanf("%d%d%d", &a, &b, &c);
addedge(a, b, c);
}
Dijkstra(n, 1);
Out(dist[n]);
// printf("%d\n", dist[n]);
}

// 伪装的差分约束系统(裸的最短路),输入输出TLE,上输入输出挂

POJ-1502 MPI Maelstrom

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// POJ-1502 MPI Maelstrom
// https://vjudge.net/problem/POJ-1502

#include <string.h>
#include <cstdio>
#include <queue>
#include <vector>
// #include <sstream>
// #include <iostream>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1000;

struct qnode {
int v, c;
qnode(int _v = 0, int _c = 0) : v(_v), c(_c){};
bool operator<(const qnode &r) const { return c > r.c; }
};

struct Edge {
int v, cost;
Edge(int _v = 0, int _cost = 0) : v(_v), cost(_cost) {}
};
vector<Edge> E[MAXN];
bool vis[MAXN];
int dist[MAXN];

//点的编号从 1 开始

void Dijkstra(int n, int start) {
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) dist[i] = INF;
priority_queue<qnode> que;
while (!que.empty()) que.pop();
dist[start] = 0;
que.push(qnode(start, 0));
qnode tmp;
while (!que.empty()) {
tmp = que.top();
que.pop();
int u = tmp.v;
if (vis[u]) continue;
vis[u] = true;
for (int i = 0; i < E[u].size(); i++) {
int v = E[tmp.v][i].v;
int cost = E[u][i].cost;
if (!vis[v] && dist[v] > dist[u] + cost) {
dist[v] = dist[u] + cost;
que.push(qnode(v, dist[v]));
}
}
}
}
void addedge(int u, int v, int w) { E[u].push_back(Edge(v, w)); }

int main() {
int n;
scanf("%d", &n);
char str[100];
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i - 1; j++) {
// string s;
// cin >> s;
// if (s[0] == 'x') continue;
// stringstream ss;
// ss << s;
// ss >> tmp;
scanf("%s", str);
if (str[0] == 'x') continue;
int tmp = atoi(str);
addedge(i, j, tmp);
addedge(j, i, tmp);
}
}
Dijkstra(n, 1);
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, dist[i]);
}
printf("%d\n", ans);
return 0;
}

// 从 1 出发最短路中的最长路

POJ-3660 Cow Contest

Floyd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// POJ-3660 Cow Contest
// https://vjudge.net/problem/POJ-3660

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int MAXN = 105;
int dist[MAXN][MAXN];

void floyd(int n) {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = (dist[i][j] || (dist[i][k] && dist[k][j]));
}
}
}
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
memset(dist, 0, sizeof(dist));
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d%d", &a, &b);
dist[a][b] = 1;
}
floyd(n);
int ans = 0;
for (int i = 1; i <= n; i++) {
int cnt = 0;
for (int j = 1; j <= n; j++) {
if (dist[i][j] || dist[j][i]) cnt++;
}
if (cnt >= n - 1) {
ans++;
}
}
printf("%d\n", ans);

return 0;
}

// 传递闭包

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// POJ-3660 Cow Contest
// https://vjudge.net/problem/POJ-3660

#include <string.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <vector>
using namespace std;

const int MAXN = 105;
int n, m;
vector<int> ed[MAXN];
int vis[MAXN][MAXN]; // vis[i][j]表示i->j可达
void dfs(int s) //普通的dfs算法
{
int num = n;
stack<int> st;
st.push(s);
vis[s][s] = 1;
while (!st.empty()) {
int now = st.top();
st.pop();
int len = ed[now].size();
for (int i = 0; i < len; ++i) {
if (vis[s][ed[now][i]] == 0) {
st.push(ed[now][i]);
vis[s][ed[now][i]] = 1;
}
}
}
}

int main() {
scanf("%d%d", &n, &m);
memset(vis, 0, sizeof(vis));
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d%d", &a, &b);
ed[a].push_back(b);
// vis[a][b] = 1;
}
for (int i = 1; i <= n; i++) {
dfs(i);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
int cnt = 0;
for (int j = 1; j <= n; j++) {
if (i == j) continue;
if (vis[i][j] || vis[j][i]) cnt++;
}
if (cnt >= n - 1) {
ans++;
}
}
printf("%d\n", ans);

return 0;
}

// 传递闭包

POJ-2240 Arbitrage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
// POJ-2240 Arbitrage
// https://vjudge.net/problem/POJ-2240

#include <string.h>
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
using namespace std;

const int MAXN = 1010;
const int INF = 0x3f3f3f3f;
struct Edge {
int v;
double cost;
Edge(int _v = 0, double _cost = 0) : v(_v), cost(_cost) {}
};
vector<Edge> E[MAXN];
void addedge(int u, int v, double w) { E[u].push_back(Edge(v, w)); }
bool vis[MAXN]; //在队列标志
int cnt[MAXN]; //每个点的入队列次数
double dist[MAXN];

bool SPFA(int start, int n) {
memset(vis, false, sizeof(vis));
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i <= n; i++) dist[i] = 0;
vis[start] = true;
dist[start] = 100;
queue<int> que;
que.push(start);
memset(cnt, 0, sizeof(cnt));
cnt[start] = 1;
while (!que.empty()) {
int u = que.front();
que.pop();
vis[u] = false;
for (int i = 0; i < E[u].size(); i++) {
int v = E[u][i].v;
if (dist[v] < dist[u] * E[u][i].cost) {
dist[v] = dist[u] * E[u][i].cost;
if (!vis[v]) {
vis[v] = true;
que.push(v);
if (++cnt[v] > n) return false;
// cnt[i] 为入队列次数,用来判定是否存在负环回路
}
}
}
}
return true;
}

int main() {
int Case = 1;
while (true) {
int n;
cin >> n;
if (n == 0) break;
for (int i = 0; i < MAXN; i++) {
E[i].clear();
}
map<string, int> name;
for (int i = 1; i <= n; i++) {
string str;
cin >> str;
name[str] = i;
}
int m;
cin >> m;
for (int i = 0; i < m; i++) {
string a, b;
double x;
cin >> a >> x >> b;
addedge(name[a], name[b], x);
}
cout << "Case " << Case++ << ": ";
if (!SPFA(1, n)) {
cout << "Yes";
} else {
cout << "No";
}
cout << endl;
}
return 0;
}

// SPFA 判断正环

POJ-1511 Invitation Cards

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// POJ-1511 Invitation Cards
// https://vjudge.net/problem/POJ-1511

#include <string.h>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1000005;

struct qnode {
int v, c;
qnode(int _v = 0, int _c = 0) : v(_v), c(_c){};
bool operator<(const qnode &r) const { return c > r.c; }
};

struct Edge {
int u, v, cost;
Edge(int _u = 0, int _v = 0, int _cost = 0) : u(_u), v(_v), cost(_cost) {}
};
vector<Edge> E[MAXN];
vector<Edge> Etmp;

bool vis[MAXN];
int dist[MAXN];
int tdist[MAXN];
//点的编号从 1 开始


void Dijkstra(int n, int start) {
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) dist[i] = INF;
priority_queue<qnode> que;
while (!que.empty()) que.pop();
dist[start] = 0;
que.push(qnode(start, 0));
qnode tmp;
while (!que.empty()) {
tmp = que.top();
que.pop();
int u = tmp.v;
if (vis[u]) continue;
vis[u] = true;
for (int i = 0; i < E[u].size(); i++) {
int v = E[tmp.v][i].v;
int cost = E[u][i].cost;
if (!vis[v] && dist[v] > dist[u] + cost) {
dist[v] = dist[u] + cost;
que.push(qnode(v, dist[v]));
}
}
}
}
void addedge(int u, int v, int w) { E[u].push_back(Edge(u, v, w)); }

int main() {
int T;
scanf("%d", &T);
while (T--) {
int n, m;
scanf("%d%d", &n, &m);
Etmp.clear();
for (int i = 1; i <= n; i++) {
E[i].clear();
}
for (int i = 0; i < m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
addedge(a, b, c);
Etmp.push_back(Edge(a, b, c));
}
Dijkstra(n, 1);
long long int sum = 0;
for (int i = 1; i <= n; i++) {
sum += dist[i];
E[i].clear();
}
for (int i = 0; i < m; i++) {
addedge(Etmp[i].v, Etmp[i].u, Etmp[i].cost);
}
Dijkstra(n, 1);
for (int i = 1; i <= n; i++) {
sum += dist[i];
}
printf("%lld\n", sum);
}

return 0;
}

// 求 1 到所有点再返回的最短路径长度求和,sum需要 long long
// 与 POJ-3268 Silver Cow Party 类似,将边反向再求一次即可

POJ-1847 Tram

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// POJ-1847 Tram
// https://vjudge.net/problem/POJ-1847

#include <string.h>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 1010;
const int INF = 0x3f3f3f3f;
struct Edge {
int v;
int cost;
Edge(int _v = 0, int _cost = 0) : v(_v), cost(_cost) {}
};
vector<Edge> E[MAXN];
void addedge(int u, int v, int w) { E[u].push_back(Edge(v, w)); }
bool vis[MAXN]; //在队列标志
int cnt[MAXN]; //每个点的入队列次数
int dist[MAXN];

bool SPFA(int start, int n) {
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) dist[i] = INF;
vis[start] = true;
dist[start] = 0;
queue<int> que;
que.push(start);
memset(cnt, 0, sizeof(cnt));
cnt[start] = 1;
while (!que.empty()) {
int u = que.front();
que.pop();
vis[u] = false;
for (int i = 0; i < E[u].size(); i++) {
int v = E[u][i].v;
if (dist[v] > dist[u] + E[u][i].cost) {
dist[v] = dist[u] + E[u][i].cost;
if (!vis[v]) {
vis[v] = true;
que.push(v);
if (++cnt[v] > n) return false;
// cnt[i] 为入队列次数,用来判定是否存在负环回路
}
}
}
}
return true;
}

int main() {
int N, A, B;
scanf("%d%d%d", &N, &A, &B);
for (int i = 1; i <= N; i++) {
int ct, a;
scanf("%d%d", &ct, &a);
addedge(i, a, 0);
for (int j = 1; j < ct; j++) {
scanf("%d", &a);
addedge(i, a, 1);
}
}
SPFA(A, N);
if (dist[B] != INF) {
printf("%d\n", dist[B]);
} else {
printf("-1\n");
}
return 0;
}

// 裸最短路,SPFA,Dij 都可以

POJ-1062 昂贵的聘礼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// POJ-1062 昂贵的聘礼
// https://vjudge.net/problem/POJ-1062

#include <string.h>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;

int M, N;

const int MAXN = 1010;
const int INF = 0x3f3f3f3f;
struct Edge {
int v;
int cost;
Edge(int _v = 0, int _cost = 0) : v(_v), cost(_cost) {}
};
vector<Edge> E[MAXN];
void addedge(int u, int v, int w) { E[u].push_back(Edge(v, w)); }

long long degree[MAXN];
bool vis[MAXN]; //在队列标志
int cnt[MAXN]; //每个点的入队列次数
long long dist[MAXN];

bool SPFA(int start, int n, int a, int b) {
memset(vis, false, sizeof(vis));
memset(dist, 0x3f, sizeof(dist));

vis[start] = true;
dist[start] = 0;
queue<int> que;
que.push(start);
memset(cnt, 0, sizeof(cnt));
cnt[start] = 1;
while (!que.empty()) {
int u = que.front();
que.pop();
vis[u] = false;
for (int i = 0; i < E[u].size(); i++) {
int v = E[u][i].v;
if (degree[v] < a || degree[v] > b) {
continue;
}
if (dist[v] > dist[u] + E[u][i].cost) {
dist[v] = dist[u] + E[u][i].cost;
if (!vis[v]) {
vis[v] = true;
que.push(v);
if (++cnt[v] > n) return false;
// cnt[i] 为入队列次数,用来判定是否存在负环回路
}
}
}
}
return true;
}

int main() {
scanf("%d%d", &M, &N);
for (int i = 0; i <= N; i++) {
E[i].clear();
}

long long mind = 100000, maxd = 0;
for (int i = 1; i <= N; i++) {
int w, X;
scanf("%d%lld%d", &w, &degree[i], &X);

mind = min(mind, degree[i]);
maxd = max(maxd, degree[i]);
addedge(0, i, w);
for (int j = 0; j < X; j++) {
int T, V;
scanf("%d%d", &T, &V);
addedge(T, i, V);
}
}
long long ans = E[0][0].cost;
for (int i = degree[1] - M; i <= degree[1]; i++) {
SPFA(0, N, i, i + M);
ans = min(ans, dist[1]);
}
cout << ans << endl;
}

POJ-3159 Candies

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// POJ-3159 Candies
// https://vjudge.net/problem/POJ-3159

#include <string.h>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

int Scan() { //输入外挂
int res = 0, flag = 0;
char ch;
if ((ch = getchar()) == '-')
flag = 1;
else if (ch >= '0' && ch <= '9')
res = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') res = res * 10 + (ch - '0');
return flag ? -res : res;
}

void Out(int a) { //输出外挂
if (a < 0) {
putchar('-');
a = -a;
}
if (a >= 10) Out(a / 10);
putchar(a % 10 + '0');
}
const int INF = 0x3f3f3f3f;
const int MAXN = 30005;

struct qnode {
int v, c;
qnode(int _v = 0, int _c = 0) : v(_v), c(_c){};
bool operator<(const qnode &r) const { return c > r.c; }
};

struct Edge {
int v, cost;
Edge(int _v = 0, int _cost = 0) : v(_v), cost(_cost) {}
};
vector<Edge> E[MAXN];
bool vis[MAXN];
int dist[MAXN];

//点的编号从 1 开始

void Dijkstra(int n, int start) {
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) dist[i] = INF;
priority_queue<qnode> que;
while (!que.empty()) que.pop();
dist[start] = 0;
que.push(qnode(start, 0));
qnode tmp;
while (!que.empty()) {
tmp = que.top();
que.pop();
int u = tmp.v;
if (vis[u]) continue;
vis[u] = true;
for (int i = 0; i < E[u].size(); i++) {
int v = E[tmp.v][i].v;
int cost = E[u][i].cost;
if (!vis[v] && dist[v] > dist[u] + cost) {
dist[v] = dist[u] + cost;
que.push(qnode(v, dist[v]));
}
}
}
}
void addedge(int u, int v, int w) { E[u].push_back(Edge(v, w)); }
int main() {
int n, m;
n = Scan();
m = Scan();
// scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
int a, b, c;
a = Scan();
b = Scan();
c = Scan();
// scanf("%d%d%d", &a, &b, &c);
addedge(a, b, c);
}
Dijkstra(n, 1);
Out(dist[n]);
// printf("%d\n", dist[n]);
}

// 伪装的差分约束系统(裸的最短路),输入输出TLE,上输入输出挂

POJ-2502 Subway

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
// POJ-2502 Subway
// https://vjudge.net/problem/POJ-2502

#include <string.h>
#include <cmath>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1000010;

struct qnode {
int v;
double c;
qnode(int _v = 0, double _c = 0) : v(_v), c(_c){};
bool operator<(const qnode &r) const { return c > r.c; }
};

struct Edge {
int v;
double cost;
Edge(int _v = 0, double _cost = 0) : v(_v), cost(_cost) {}
};
vector<Edge> E[MAXN];
bool vis[MAXN];
double dist[MAXN];

//点的编号从 1 开始

void Dijkstra(int n, int start) {
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) dist[i] = INF;
priority_queue<qnode> que;
while (!que.empty()) que.pop();
dist[start] = 0;
que.push(qnode(start, 0));
qnode tmp;
while (!que.empty()) {
tmp = que.top();
que.pop();
int u = tmp.v;
if (vis[u]) continue;
vis[u] = true;
for (int i = 0; i < E[u].size(); i++) {
int v = E[tmp.v][i].v;
int cost = E[u][i].cost;
if (!vis[v] && dist[v] > dist[u] + cost) {
dist[v] = dist[u] + cost;
que.push(qnode(v, dist[v]));
}
}
}
}
void addedge(int u, int v, double w) { E[u].push_back(Edge(v, w)); }

double xx[300];
double yy[300];

double len(int a, int b) {
return sqrt((xx[a] - xx[b]) * (xx[a] - xx[b]) +
(yy[a] - yy[b]) * (yy[a] - yy[b]));
}

int main() {
int cnt = 1;
scanf("%lf%lf", &xx[cnt], &yy[cnt]);
cnt++;
scanf("%lf%lf", &xx[cnt], &yy[cnt]);
cnt++;
while (~scanf("%lf%lf", &xx[cnt], &yy[cnt])) {
vector<int> subway;
subway.push_back(cnt);
cnt++;
while (xx[cnt - 1] != -1 && yy[cnt - 1] != -1) {
scanf("%lf%lf", &xx[cnt], &yy[cnt]);
subway.push_back(cnt);
cnt++;
}
cnt--;
for (int i = 0; i < subway.size() - 2; i++) {
addedge(subway[i], subway[i + 1],
len(subway[i], subway[i + 1]) / 40 * 60);
addedge(subway[i + 1], subway[i],
len(subway[i], subway[i + 1]) / 40 * 60);
}
}
for (int i = 1; i <= cnt; i++) {
for (int j = 1; j <= cnt; j++) {
if (i == j) continue;
addedge(i, j, len(i, j) / 10 * 60);
}
}
Dijkstra(cnt, 1);
printf("%d\n", int(dist[2] / 1000 + 0.5));
}

// 水题,连边麻烦一点,输入也麻烦
// 地铁只能一站一站的走
// 结果要输出整数,竟然要四舍五入!!!

POJ-3169 Layout

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// POJ-3169 Layout
// https://vjudge.net/problem/POJ-3169

#include <string.h>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 1010;
const int INF = 0x3f3f3f3f;
struct Edge {
int v;
int cost;
Edge(int _v = 0, int _cost = 0) : v(_v), cost(_cost) {}
};
vector<Edge> E[MAXN];
void addedge(int u, int v, int w) { E[u].push_back(Edge(v, w)); }
bool vis[MAXN]; //在队列标志
int cnt[MAXN]; //每个点的入队列次数
int dist[MAXN];

bool SPFA(int start, int n) {
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) dist[i] = INF;
vis[start] = true;
dist[start] = 0;
queue<int> que;
que.push(start);
memset(cnt, 0, sizeof(cnt));
cnt[start] = 1;
while (!que.empty()) {
int u = que.front();
que.pop();
vis[u] = false;
for (int i = 0; i < E[u].size(); i++) {
int v = E[u][i].v;
if (dist[v] > dist[u] + E[u][i].cost) {
dist[v] = dist[u] + E[u][i].cost;
if (!vis[v]) {
vis[v] = true;
que.push(v);
if (++cnt[v] > n) return false;
// cnt[i] 为入队列次数,用来判定是否存在负环回路
}
}
}
}
return true;
}

int main() {
int N, ML, MD;
scanf("%d%d%d", &N, &ML, &MD);
for (int i = 0; i < ML; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
addedge(a, b, c);
}
for (int i = 0; i < MD; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
addedge(b, a, -c);
}
if (SPFA(1, N)) {
if (dist[N] == INF) {
printf("-2");
} else {
printf("%d", dist[N]);
}
} else {
printf("-1");
}
printf("\n");
}

// 差分约束系统
// A - B <= D -> add(A,B,D)
// A - B >= D -> 同乘 - 1得 B - A <= -D -> add(B,A,-D)

LightOJ-1074 Extended Traffic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// LightOJ-1074 Extended Traffic
// https://vjudge.net/problem/LightOJ-1074

#include <string.h>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 1010;
const int INF = 0x3f3f3f3f;
struct Edge {
int v;
int cost;
Edge(int _v = 0, int _cost = 0) : v(_v), cost(_cost) {}
};
vector<Edge> E[MAXN];
void addedge(int u, int v, int w) { E[u].push_back(Edge(v, w)); }
bool vis[MAXN]; //在队列标志
int cnt[MAXN]; //每个点的入队列次数
int dist[MAXN];

bool SPFA(int start, int n) {
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) dist[i] = INF;
vis[start] = true;
dist[start] = 0;
queue<int> que;
que.push(start);
memset(cnt, 0, sizeof(cnt));
cnt[start] = 1;
while (!que.empty()) {
int u = que.front();
que.pop();
vis[u] = false;
for (int i = 0; i < E[u].size(); i++) {
int v = E[u][i].v;
if (dist[v] > dist[u] + E[u][i].cost) {
dist[v] = dist[u] + E[u][i].cost;
if (!vis[v]) {
vis[v] = true;
if (++cnt[v] > n) {
dist[v] = -INF;
} else {
que.push(v);
}
// cnt[i] 为入队列次数,用来判定是否存在负环回路
}
}
}
}
return true;
}
int arr[MAXN];

int main() {
int T;
scanf("%d", &T);
for (int Case = 1; Case <= T; Case++) {
for (int i = 0; i < MAXN; i++) {
E[i].clear();
}
printf("Case %d:\n", Case);
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &arr[i]);
}
int m;
scanf("%d", &m);
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d%d", &a, &b);
addedge(a, b, (arr[b] - arr[a]) * (arr[b] - arr[a]) * (arr[b] - arr[a]));
}
bool flag = SPFA(1, n);
int q;
scanf("%d", &q);
for (int i = 0; i < q; i++) {
int x, ans;
scanf("%d", &x);
if (dist[x] == INF || dist[x] < 3) {
printf("?\n");
} else {
printf("%d\n", dist[x]);
}
}
}
}

// SPFA 判断**所有负环**

HDU-4725 The Shortest Path in Nya Graph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
// HDU-4725 The Shortest Path in Nya Graph
// https://vjudge.net/problem/HDU-4725

#include <string.h>
#include <cmath>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 300005;

struct qnode {
int v, c;
qnode(int _v = 0, int _c = 0) : v(_v), c(_c){};
bool operator<(const qnode &r) const { return c > r.c; }
};

struct Edge {
int v, cost;
Edge(int _v = 0, int _cost = 0) : v(_v), cost(_cost) {}
};
vector<Edge> E[MAXN];
bool vis[MAXN];
int dist[MAXN];

//点的编号从 1 开始

void Dijkstra(int n, int start) {
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) dist[i] = INF;
priority_queue<qnode> que;
while (!que.empty()) que.pop();
dist[start] = 0;
que.push(qnode(start, 0));
qnode tmp;
while (!que.empty()) {
tmp = que.top();
que.pop();
int u = tmp.v;
if (vis[u]) continue;
vis[u] = true;
for (int i = 0; i < E[u].size(); i++) {
int v = E[tmp.v][i].v;
int cost = E[u][i].cost;
if (!vis[v] && dist[v] > dist[u] + cost) {
dist[v] = dist[u] + cost;
que.push(qnode(v, dist[v]));
}
}
}
}
void addedge(int u, int v, int w) { E[u].push_back(Edge(v, w)); }
int arr[MAXN];
int flag[MAXN];
int main() {
int T;
scanf("%d", &T);
for (int Case = 1; Case <= T; Case++) {
int N, M, C;
scanf("%d%d%d", &N, &M, &C);
memset(flag, 0, sizeof(flag));
for (int i = 1; i <= N * 3; i++) {
E[i].clear();
}
for (int i = 1; i <= N; i++) {
scanf("%d", &arr[i]);
flag[arr[i]]++;

addedge(i, arr[i] + N + 1 + 1, 0);
addedge(i, arr[i] + N + 1 - 1, 0);

addedge(arr[i] + N + 1, i, C);
}

for (int i = 0; i < M; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
addedge(a, b, c);
addedge(b, a, c);
}
Dijkstra(N * 3, 1);
printf("Case #%d: ", Case);
if (dist[N] == INF) {
printf("%d\n", -1);
} else {
printf("%d\n", dist[N]);
}
}
}

// 建图困难一些的最短路问题,如果完全按题意建图会超时
// 将层抽象成虚点,点到相邻层的虚点连一条 0
// 边权的虚边,虚点到当前层的点连一条 C 边权的边

HDU-3416 Marriage Match IV

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
// HDU-3416 Marriage Match IV
// https://vjudge.net/problem/HDU-3416

#include <string.h>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 2000;

struct qnode {
int v, c;
qnode(int _v = 0, int _c = 0) : v(_v), c(_c){};
bool operator<(const qnode &r) const { return c > r.c; }
};

struct Edge {
int u, v, cost;
Edge(int _u = 0, int _v = 0, int _cost = 0) : u(_u), v(_v), cost(_cost) {}
};
vector<Edge> E[MAXN];
vector<Edge> Ex;
bool vis[MAXN];
int dist[MAXN];

//点的编号从 1 开始

void Dijkstra(int n, int start) {
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) dist[i] = INF;
priority_queue<qnode> que;
while (!que.empty()) que.pop();
dist[start] = 0;
que.push(qnode(start, 0));
qnode tmp;
while (!que.empty()) {
tmp = que.top();
que.pop();
int u = tmp.v;
if (vis[u]) continue;
vis[u] = true;
for (int i = 0; i < E[u].size(); i++) {
int v = E[tmp.v][i].v;
int cost = E[u][i].cost;
if (!vis[v] && dist[v] > dist[u] + cost) {
dist[v] = dist[u] + cost;
que.push(qnode(v, dist[v]));
}
}
}
}
void addedge(int u, int v, int w) { E[u].push_back(Edge(u, v, w)); }

const int MAXM = 1200010;
struct Edgef {
int to, next, cap, flow;
} edge[MAXM];
int tol;
int head[MAXN];
void init() {
tol = 2;
memset(head, -1, sizeof(head));
}
void addedge(int u, int v, int w, int rw) {
edge[tol].to = v;
edge[tol].cap = w;
edge[tol].flow = 0;
edge[tol].next = head[u];
head[u] = tol++;
edge[tol].to = u;
edge[tol].cap = rw;
edge[tol].flow = 0;
edge[tol].next = head[v];
head[v] = tol++;
}
int Q[MAXN];
int dep[MAXN], cur[MAXN], sta[MAXN];
bool bfs(int s, int t, int n) {
int front = 0, tail = 0;
memset(dep, -1, sizeof(dep[0]) * (n + 1));
dep[s] = 0;
Q[tail++] = s;
while (front < tail) {
int u = Q[front++];
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if (edge[i].cap > edge[i].flow && dep[v] == -1) {
dep[v] = dep[u] + 1;
if (v == t) return true;
Q[tail++] = v;
}
}
}
return false;
}

int dinic(int s, int t, int n) {
int maxflow = 0;
while (bfs(s, t, n)) {
for (int i = 0; i < n; i++) {
cur[i] = head[i];
}
int u = s, tail = 0;
while (cur[s] != -1) {
if (u == t) {
int tp = INF;
for (int i = tail - 1; i >= 0; i--) {
tp = min(tp, edge[sta[i]].cap - edge[sta[i]].flow);
}
maxflow += tp;
for (int i = tail - 1; i >= 0; i--) {
edge[sta[i]].flow += tp;
edge[sta[i] ^ 1].flow -= tp;

if (edge[sta[i]].cap - edge[sta[i]].flow == 0) tail = i;
}
u = edge[sta[tail] ^ 1].to;
} else if (cur[u] != -1 && edge[cur[u]].cap > edge[cur[u]].flow &&
dep[u] + 1 == dep[edge[cur[u]].to]) {
sta[tail++] = cur[u];
u = edge[cur[u]].to;
} else {
while (u != s && cur[u] == -1) {
u = edge[sta[--tail] ^ 1].to;
}
cur[u] = edge[cur[u]].next;
}
}
}
return maxflow;
}

int distA[MAXN];
int distB[MAXN];

int main() {
int T;
scanf("%d", &T);
while (T--) {
init();
Ex.clear();
for (int i = 0; i < MAXN; i++) {
E[i].clear();
}
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
Ex.push_back(Edge(a, b, c));
addedge(a, b, c);
}
int A, B;
scanf("%d%d", &A, &B);
Dijkstra(n, A);
memcpy(distA, dist, sizeof(dist));
for (int i = 0; i < MAXN; i++) {
E[i].clear();
}
for (int i = 0; i < Ex.size(); i++) {
addedge(Ex[i].v, Ex[i].u, Ex[i].cost);
}
Dijkstra(n, B);
memcpy(distB, dist, sizeof(dist));

for (int i = 0; i < Ex.size(); i++) {
if (distA[Ex[i].u] + distB[Ex[i].v] + Ex[i].cost == distA[B]) {
addedge(Ex[i].u, Ex[i].v, 1, 0);
}
}
int ans = dinic(A, B, n);
printf("%d\n", ans);
}
}

// 求最短路的条数(无公共边)
// 找出最短路经过的边,跑最大流
Donate comment here