1808: 地铁
- Time Limit: 5 Sec
- Memory Limit: 128 Mb
- Submitted: 2004
- Solved: 498
Description
Bobo 居住在大城市 ICPCCamp。
ICPCCamp 有 n 个地铁站，用 1,2,…,n 编号。 m 段双向的地铁线路连接 n 个地铁站，其中第 i 段地铁属于 ci 号线，位于站 ai,bi 之间，往返均需要花费 ti 分钟（即从 ai 到 bi 需要 ti 分钟，从 bi 到 ai 也需要 ti 分钟）。
众所周知，换乘线路很麻烦。如果乘坐第 i 段地铁来到地铁站 s，又乘坐第 j 段地铁离开地铁站 s，那么需要额外花费 |ci-cj | 分钟。注意，换乘只能在地铁站内进行。
Bobo 想知道从地铁站 1 到地铁站 n 所需要花费的最小时间。
Input
输入包含不超过 20 组数据。
每组数据的第一行包含两个整数 n,m ($2≤n≤10^5,1≤m≤10^5$).
接下来 m 行的第 i 行包含四个整数 $a_i,b_i,c_i,t_i (1≤a_i,b_i,c_i≤n,1≤t_i≤10^9)$.
保证存在从地铁站 1 到 n 的地铁线路（不一定直达）。
Output
对于每组数据，输出一个整数表示要求的值。
Sample Input
3 3
1 2 1 1
2 3 2 1
1 3 1 1
3 3
1 2 1 1
2 3 2 1
1 3 1 10
3 2
1 2 1 1
2 3 1 1Sample Output
1
3
2Source
湖南省第十二届大学生计算机程序设计竞赛
链接
http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1808
题意
n个点m条边的有向带权图，除了边权之外，从第i条边转到第j条边有额外的花费，问从起点1到终点n的最短路径。
题解
加了额外的花费条件之后跑最短路时就没法直接用点来进行更新，因为不能确定是从哪一条边跳转到当前节点。
我们可以对边进行操作，dist[i]表示起点到第i条边的最短路径，如果$edge[i].to == n$，就可以返回结果了。
我一开始的做法是使用一个结构体保存两个信息：起点到点i的最短路径dist[i]，以及通往改点的边的编号，最后进行更新操作时还是用点来完成的，但是这样是错的，当dist[i]相同的时候，就没法确定是哪条边到该节点的，所以会导致在转换路线的时候出现错误，想了很久。
这题，不能用点来做，因为对于同一个点，可能从不同的边来，你d记录的是当前这个点的最小值，但是可能下一次更新的，不一定是从当前这个最小值出去的，可能是从一个大一点，但是加上额外花费之后，就最小了。也就是说：如果A到C的最短路一定要经过B，那么A到C的最短路等于A到B的最短路+B到C的最短路。 这个结论在这个题里是不成立的。因为不同的A-B的地铁线路，可能会导致不同的B-C最短路的走法。 我好像明白了。。谢谢菊苣指点
——转自CSDN：传送门
代码
| Status | Accepted |
|---|---|
| Time | 1028ms |
| Memory | 23452kB |
| Length | 2090 |
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 200010;
int n, m, tot;
int head[maxn];
ll dist[maxn];
bool vis[maxn];
struct qnode
{
int idx; // 边的编号
ll time; // 时间
qnode(int _idx = 0, ll _time = 0): idx(_idx), time(_time) {}
bool operator < (const qnode &r)const
{
return time > r.time;
}
};
struct Edge
{
int to, next;
ll time, cost;
}edge[maxn << 2];
void init()
{
memset(head, -1, sizeof(head));
tot = 0;
}
void addedge(int u, int v, ll c, ll t)
{
edge[tot].to = v; // 下一个节点
edge[tot].time = t; // 时间
edge[tot].cost = c; // 换乘时间
edge[tot].next = head[u];
head[u] = tot++;
}
ll dijkstra(int st)
{
memset(vis, 0, sizeof(vis));
for (int i = 0; i < tot; ++i) // 每条边到起点的最短路径
dist[i] = inf;
priority_queue <qnode> Q;
while (!Q.empty())
Q.pop();
for (int i = head[st]; i != -1; i = edge[i].next) // 与起点相连的顶点的边入队
{
dist[i] = edge[i].time;
Q.push(qnode(i, dist[i]));
}
qnode tmp;
while (!Q.empty())
{
tmp = Q.top();
Q.pop();
int idx = tmp.idx;
int u = edge[idx].to;
if (u == n) // 到达终点，直接返回
return dist[idx];
if (vis[idx])
continue;
vis[idx] = true;
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
ll time = edge[i].time;
ll cost = abs(edge[idx].cost - edge[i].cost);
if (!vis[i] && dist[i] > dist[idx] + time + cost) // 更新
{
dist[i] = dist[idx] + time + cost;
Q.push(qnode(i, dist[i]));
}
}
}
}
int main()
{
int a, b;
ll c, t;
while (scanf("%d%d", &n, &m) != EOF)
{
init();
for (int i = 0; i < m; ++i)
{
scanf("%d%d%lld%lld", &a, &b, &c, &t);
addedge(a, b, c, t);
addedge(b, a, c, t);
}
printf("%lld\n", dijkstra(1));
}
return 0;
}- 错误代码
void dijkstra(int st)
{
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; ++i)
dist[i] = inf;
priority_queue <qnode> Q;
while (!Q.empty())
Q.pop();
for (int i = head[st]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
dist[v] = edge[i].time;
Q.push(qnode(i, dist[v]));
}
qnode tmp;
while (!Q.empty())
{
tmp = Q.top();
Q.pop();
int idx = tmp.idx;
int u = edge[idx].to;
if (vis[u])
continue;
vis[u] = true;
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
ll time = edge[i].time;
ll cost = abs(edge[idx].cost - edge[i].cost);
if (!vis[v] && dist[v] > dist[u] + time + cost)
{
dist[v] = dist[u] + time + cost;
Q.push(qnode(i, dist[v]));
}
}
}
}最短路每年都考，但是每年都玩出新花样。
The end.
2018-08-09 星期四