OneDay的最短路

发布时间: 2018年8月21日 10:52   最后更新: 2018年8月23日 18:22   时间限制: 1000ms   内存限制: 256M   SPJ

OneDay同学是图论大师,每次比赛都可以给你五分钟AC一道图论题。

今天CSL又出了一道图论题想把OneDay难到:

求最短路

时间限制 1s 空间限制 256MB

给定一个$n$个点$m$条边的有向图,边权为正,求从$1$结点出发到$n$结点的最短路。

输入描述

  • 第一行两个整数$n,m$ ($1 \le n \le 10^{5},1 \le m \le 4 \times 10 ^{5}$) 表示图的顶点数目和边的数目。
  • 接下来$m$行每行三个整数 $u, v, w$($1 \le u,v \le n$, $1 \le w \le 1000$),表示从编号为$u$的点到编号为$v$的点存在一条边权为$w$的边,保证没有重边和自环。

输出描述

一行一个整数表示从$1$到$n$的最短路的长度,若不存在最短路,则输出$-1$。

样例输入

4 6
1 2 1
1 3 2
1 4 6
2 3 1
3 4 2
2 4 4

样例输出

4

OneDay凭借他高潮的技巧,又在5分钟里自动AC了这题。CSL非常生气,觉得OneDay的这种假算法应该被卡掉,就问Lonelam要了OJ的管理员账号到后台看到了OneDay的AC代码。

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif
    int n, m;
    scanf("%d%d", &n, &m);
    vector<vector<pair<int, int>>> G(n + 1);
    for (int i = 0, u, v, w; i < m; i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        G[u].emplace_back(v, w);
    }
    vector<int> d(n + 1, INF), inq(n + 1);
    queue<int> q;
    q.push(1);
    inq[1] = 1;
    d[1] = 0;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        inq[u] = 0;
        for (auto& e : G[u])
        {
            int &v = e.first, &w = e.second;
            if (d[u] + w < d[v])
            {   // 松弛操作
                d[v] = d[u] + w;
                // 没有入队就入队
                if (!inq[v]) q.push(v), inq[v] = 1;
            }
        }
    }
    printf("%d\n", d[n] == INF ? -1 : d[n]);
    return 0;
}

CSL决定出一组数据卡掉这个奇怪的算法,可是他现在非常忙,就把这个锅甩给了你。

无输入

第一行两个整数$n,m$ ($1 \le n \le 10^{5},1 \le m \le 4 \times 10 ^{5}$) 表示图的顶点数目和边的数目。
接下来$m$行每行三个整数 $u, v, w$($1 \le u,v \le n$, $1 \le w \le 1000$),表示从编号为$u$的点到编号为$v$的点存在一条边权为$w$的边,保证没有重边和自环。

复制
no input
3 2
1 2 3
2 3 1

样例输出仅表示输出格式,并不能通过此题。

graph theory

CSL