Posts Tagged ‘K短路’

POJ 2449 Remmarguts’ Date

Posted in PKU OJ on 五月 13th, 2010 by 纳米 – Be the first to comment

这道题是五一那天在学校做的。我没有读题，只知道题目意思如下：
输入格式：
n, m
u_1, v_1, w_1
…
u_m, v_m, w_m
s, t, k
求s到t的第k短路。

解题报告：
利用A*搜索，具体此题题解网上一大摞，我就不说了。我是用spfa算最短路和手写堆的，没有用dijkstra和STL的优先级队列（其实是因为不会用STL -_-|||）。

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

#include <stdio.h>
#include <string.h>
 
const int maxn = 1003, maxm = 100003;
int n, m, s, t, k, el[maxm][3];
int dist[maxn], heap[maxn*maxn][3], tt;
int answer;
 
struct EDGE {
	int v, l;
};
 
int input() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i)
		scanf("%d%d%d", &el[i][0], &el[i][1], &el[i][2]);
	scanf("%d%d%d", &s, &t, &k);
	if (s == t)
		++k;
	return 0;
}
 
int spfa() {
	EDGE *edge[maxn];
	int et[maxn] = {0};
	for (int i = 1; i <= m; ++i)
		++et[el[i][1]];
	for (int i = 1; i <= n; ++i)
		edge[i] = new EDGE [et[i] + 1];
	memset(et, 0, sizeof(et));
	for (int i = 1; i <= m; ++i) {
		int u = el[i][1], v = el[i][0];
		edge[u][et[u]].v = v;
		edge[u][et[u]].l = el[i][2];
		++et[u];
	}
	int q[maxn], head = -1, last = 0;
	bool vis[maxn] = {0};
	q[0] = t;
	vis[t] = true;
	for (int i = 1; i <= n; ++i)
		dist[i] = 0x7FFFFFFF;
	dist[t] = 0;
	while (head < last) {
		int u = q[++head % maxn];
		vis[u] = false;
		for (int i = 0, v = edge[u][0].v; i < et[u]; v = edge[u][++i].v)
			if (dist[u] + edge[u][i].l < dist[v]) {
				dist[v] = edge[u][i].l + dist[u];
				if (!vis[v]) {
					q[++last % maxn] = v;
					vis[v] = true;
				}
			}
	}
	return 0;
}
 
bool empty() {
	return tt == 0;
}
 
void swap(int w0, int w1) {
	int temp;
	temp = heap[w0][0]; heap[w0][0] = heap[w1][0]; heap[w1][0] = temp;
	temp = heap[w0][1]; heap[w0][1] = heap[w1][1]; heap[w1][1] = temp;
	temp = heap[w0][2]; heap[w0][2] = heap[w1][2]; heap[w1][2] = temp;
}
 
void insert(int key0, int key1, int key2) {
	int t = ++tt;
	heap[tt][0] = key0;
	heap[tt][1] = key1;
	heap[tt][2] = key2;
	while (t > 1 && heap[t][0] < heap[t >> 1][0]) {
		swap(t, t >> 1);
		t >>= 1;
	}
}
 
void keep(int t) {
	int left = t << 1;
	int right = left + 1;
	int mint = t;
	if (left <= tt)
		mint = heap[left][0] < heap[mint][0] ? left : mint;
	if (right <= tt)
		mint = heap[right][0] < heap[mint][0] ? right : mint;
	if (mint != t) {
		swap(mint, t);
		keep(mint);
	}
}
 
void pop(int &key0, int &key1, int &key2) {
	key0 = heap[1][0], key1 = heap[1][1], key2 = heap[1][2];
	if (tt > 1) {
		swap(1, tt--);
		keep(1);
	} else {
		tt = 0;
	}
}
 
int work() {
	EDGE *edge[maxn];
	int et[maxn] = {0}, its[maxn] = {0}, ots[maxn] = {0};
	for (int i = 1; i <= m; ++i)
		++et[el[i][0]];
	for (int i = 1; i <= n; ++i)
		edge[i] = new EDGE [et[i] + 1];
	memset(et, 0, sizeof(et));
	for (int i = 1; i <= m; ++i) {
		int u = el[i][0], v = el[i][1];
		edge[u][et[u]].v = v;
		edge[u][et[u]].l = el[i][2];
		++et[u];
	}
	tt = 0;
	insert(dist[s], s, 0);
	while (!empty()) {
		int c, cost, u;
		pop(c, u, cost);
		++ots[u];
		if (ots[t] == k)
			return cost;
		for (int i = 0, v = edge[u][0].v; i < et[u]; v = edge[u][++i].v)
			if (ots[v] < k)
				insert(cost + edge[u][i].l + dist[v], v, cost + edge[u][i].l);
		for (int i = 0, v = edge[u][0].v; i < et[u]; v = edge[u][++i].v)
			if (its[v] < k)
				++its[v];
	}
	return -1;
}
 
int output() {
	printf("%d\n", answer);
	return 0;
}
 
int main() {
	input();
	spfa();
	answer = work();
	output();
	return 0;
}