1021 玛丽卡
时间限制: 2 s
空间限制: 128000 KB
题目等级 : 大师 Master
题解
题目描述 Description
麦克找了个新女朋友，玛丽卡对他非常恼火并伺机报复。因为她和他们不住在同一个城市，因此她开始准备她的长途旅行。在这个国家中每两个城市之间最多只有一条路相通，并且我们知道从一个城市到另一个城市路上所需花费的时间。麦克在车中无意中听到有一条路正在维修，并且那儿正堵车，但没听清楚到底是哪一条路。无论哪一条路正在维修，从玛丽卡所在的城市都能到达麦克所在的城市。玛丽卡将只从不堵车的路上通过，并且她将按最短路线行车。麦克希望知道在最糟糕的情况下玛丽卡到达他所在的城市需要多长时间，这样他就能保证他的女朋友离开该城市足够远。
编写程序，帮助麦克找出玛丽卡按最短路线通过不堵车道路到达他所在城市所需的最长时间(用分钟表示)。
输入描述 Input Description
第一行有两个用空格隔开的数N和M，分别表示城市的数量以及城市间道路的数量。1≤N≤1000，1≤M≤N*(N-1)/2。城市用数字1至N标识，麦克在城市1中，玛丽卡在城市N中。
接下来的M行中每行包含三个用空格隔开的数A，B和V。其中1≤A，B≤N，1≤V≤1000。这些数字表示在A和城市B中间有一条双行道，并且在V分钟内是就能通过。
输出描述 Output Description
输出文件的第一行中写出用分钟表示的最长时间，在这段时间中，无论哪条路在堵车，玛丽卡应该能够到达麦克处，如果少于这个时间的话，则必定存在一条路，该条路一旦堵车，玛丽卡就不能够赶到麦克处。
样例输入 Sample Input
5 7
1 2 8
1 4 10
2 3 9
2 4 10
2 5 1
3 4 7
3 5 10
样例输出 Sample Output
27
嗯，这道题占据了鄙人，应该有8个小时了吧。整个过程那叫一个酸爽。
那么，解题过程从昨天晚上9点开始。
一开始看到这一题，以为就是一个求单源最短路、SPFA的模板题，数据不大，邻接矩阵SPFA直接就可以过了。结果仔细读完后发现要处理堵车的情况。于是就想出了一个比较暴力的办法——先进行一遍SPFA后，把最短路的路径记录下来，然后再把路径上的路依次堵车再SPFA。其中求出距离（耗时）最长的一次就是答案。因为堵车的路不在最短路上，则不会影响，所以只需要枚举将最短路上的路填成INF后，取所有更改一条边之后的最短距离的最大值
于是我开始我的第一次尝试。
邻接矩阵+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
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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
const int INF = 999999999;
using namespace std;
int map[1001][1001], dis[1001], n, m, pre[1001], vis[1001], ans=-INF;//数组pre[i]记录点i之前的一个点
void spfa(int s)//这是找路径的SPFA，要记录路径
{
int u;
dis[s] = 0;
pre[s] = -1;
vis[s] = 1;
queue<int> q;
q.push(s);
while (!q.empty())
{
u = q.front();
q.pop();
vis[u] = 0;
for (int i = 1; i <= n; i++)
{
if (map[u][i] && dis[i] > dis[u] + map[u][i])
{
dis[i] = dis[u] + map[u][i];
pre[i] = u;
if (vis[i] == 0)
{
vis[i] = 1;
q.push(i);
}
}
}
}
}
void spfa2(int s)//不要修改路径，只要求出在某条路堵车的情况下到达目的地的最少耗时
{
int u;
dis[s] = 0;
vis[s] = 1;
queue<int> q;
q.push(s);
while (!q.empty())
{
u = q.front();
q.pop();
vis[u] = 0;
for (int i = 1; i <= n; i++)
{
if (map[u][i] && dis[i] > dis[u] + map[u][i])
{
dis[i] = dis[u] + map[u][i];
if (vis[i] == 0)
{
vis[i] = 1;
q.push(i);
}
}
}
}
}
int main()
{
int a, b, c;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
dis[i] = INF;
/*for (int j = 1; j <= n; j++)
{
if (i == j)
map[i][j] = 0;
else
map[i][j] = INF;
}*/
}
for (int i = 1; i <= m; i++)
{
cin >> a >> b >> c;
map[a][b] = c;
map[b][a] = c;
}
spfa(n);
int v = 1, temp;
while (pre[v] != -1)
{
temp = map[pre[v]][v];
map[pre[v]][v] = INF;//堵车即这条路耗时无穷大
for (int i = 1; i <= n; i++)
{
dis[i] = INF;
}
spfa2(n);
map[pre[v]][v] = temp;//尝试完后记得恢复原来的不堵车的状态
if (dis[1] < INF)
{
if (dis[1] > ans)
ans = dis[1];
}
v = pre[v];
}
cout << ans;
return 0;
}
嗯，真是完美的想法，题目给的样例一遍过了。结果提交上去有一个测试点运行超时。当时百思不得其解难道还要进行什么高深的优化么？？？上网走了一下题解发现这题就是一道SPFA，那为什么我一交就一个点暴时间了呢？后来看了一下某位仁兄的博客，发现这一题用邻接矩阵确实会有一个点暴时间。。。他后来是用了邻接表存图AC的。
好，邻接表是吧，我这就去用。
第二天上午9点开始了第二次尝试，开始搜讲解邻接表的博客。这也是我最后悔的一个操作，因为我搜到一个用动态建图的邻接表博客。。。用到了结构体指针。用到这一题上我就被自己写的代码绕晕了。果然一运行程序就崩溃了。很好，那就开始调试吧。
调试结果不用想都知道是以失败告终。我的上午就这样结束了。
中午回寝把一本《图论及应用》的ACM-ICPC书籍拿到了机房开始翻看邻接表到底怎么弄，终于发现了救命稻草——链式前向星。
链式前向星就是一种静态建立邻接表的存图方法，相对于动态建表。链式前向星采用数组模拟链表的方式实现邻接表的功能，并且使用很少的额外空间，可以说是目前建图和遍历效率最高的储存方式。对于我这个用邻接矩阵用了几年的乡里娃来说可谓是鸟炮枪换大炮。
那么，第三次尝试开始。（因为没有成功就不上代码了）
样例一遍过，提交，只对了20%的测试点。
为什么？
经过一个小时的调试，我发现问题出在路径记录上面。因为存图方式已经改变，因此路径记录就不能按邻接矩阵的搞法去弄了。因为pre记录的是点与点的前驱后继关系，邻接表存的是边，每条边的编号与点无关系。因此用点去删边的话可能删去的边并不是路径上的边。
再一次恍然大悟后开始第四次尝试。
有句话说得好，历史总是惊人的相似，今天我是信了。最后一个点爆了运行错误。
原来，我又忽略了邻接表的一个要注意的地方。
这一题的图是无向图，意味着边都是双向边，因此在邻接矩阵中的一条边这里相当于两条，一条顺着一条相反。因此存边的数组要开成两倍。
第五次尝试开始：
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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#define INF 999999999
using namespace std;
int head[1001], dis[1001], ans, n, m, vis[1001], pre[1001];//head[i]表示连接点i的边在edge[]中的编号
struct edgenode
{
int to;//to表示当前边指向的下一个点的位置
int w;//表示当前边的耗时（权值）
int next;//下一条边的编号
}edge[1000001];
void spfa(bool record)//这会没有傻傻地写两个SPFA函数了，直接用一个参数record决定是否记录路径就行
{
if (record)
pre[n] = -1;
int u, k;
queue<int> q;
for (int i = 1; i <= n; i++)
dis[i] = INF;
memset(vis, 0, sizeof(vis));
q.push(n);
vis[n] = 1;
dis[n] = 0;
while (!q.empty())
{
u = q.front();
q.pop();
vis[u] = 0;
k = head[u];
while (k != 0)
{
if (dis[edge[k].to] > dis[u] + edge[k].w)
{
dis[edge[k].to] = dis[u] + edge[k].w;
if (record)
{
pre[edge[k].to] = u;
}
if (!vis[edge[k].to])
{
vis[edge[k].to] = 1;
q.push(edge[k].to);
}
}
k = edge[k].next;
}
}
}
int main()
{
cin >> n >> m;
int a, b, c;
for (int i = 1; i <= m; i++)//邻接表建立无向图的过程
{
cin >> a >> b >> c;
edge[i].to = b;
edge[i].w = c;
edge[i].next = head[a];
head[a] = i;
edge[i + m].to = a;
edge[i + m].w = c;
edge[i + m].next = head[b];
head[b] = i + m;
}
spfa(true);
int v = 1, temp, k;
ans = -INF;
while (pre[v] != -1)
{
k = head[pre[v]];
while (edge[k].to != v)//一定要找到在路径中的边才行
k = edge[k].next;
temp = edge[k].w;
edge[k].w = INF;
edge[k > m ? k - m : k + m].w = INF;//无向图反过来也要删一遍
spfa(false);
if (ans < dis[1])
ans = dis[1];
edge[k].w = temp;
edge[k > m ? k - m : k + m].w = temp;
v = pre[v];
}
cout << ans;
return 0;
}代码给出来了意味着我终于AC这一题。以上就是本题的邻接表（链式前向星）+SPFA+记录路径的AC代码了。一波三折的构成透露出鄙人浅薄的知识，各路大佬勿喷勿喷。。。。。。
最后
以上就是虚拟巨人最近收集整理的关于CodeVS1021 玛丽卡 解题报告的全部内容，更多相关CodeVS1021内容请搜索靠谱客的其他文章。
![[Wikioi 1021]玛丽卡(疑难题)](/uploads/reation/bcimg5.png)
![CODE[VS]1021 玛丽卡](/uploads/reation/bcimg6.png)
发表评论 取消回复