MENU

CSU1808 地铁(最短路+边松弛)

2018 年 08 月 09 日 • 阅读: 1232 • 图论阅读设置

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 1

Sample Output

1
3
2

Source

湖南省第十二届大学生计算机程序设计竞赛


链接

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:传送门

代码

StatusAccepted
Time1028ms
Memory23452kB
Length2090
#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 星期四
最后编辑于: 2018 年 08 月 19 日