专栏首页ACM算法日常最短路专题3| CF 20C - SPFA带环图

最短路专题3| CF 20C - SPFA带环图

C. Dijkstra?

You are given a weighted undirected graph. The vertices are enumerated from 1 to n. Your task is to find the shortest path between the vertex 1 and the vertex n.

给定一个带权重的无向图,节点从1到n。找出节点1和节点n的最短路径。

Input

The first line contains two integers n and m (), where n is the number of vertices and m is the number of edges. Following m lines contain one edge each in form , and (), where , are edge endpoints and is the length of the edge.

第一行包含2个整数n和m,n是节点数量,m是边数。接下来m条边表示节点到节点以及权重。

It is possible that the graph has loops and multiple edges between pair of vertices. 图G可能有环。

Output

Write the only integer -1 in case of no path. Write the shortest path in opposite case. If there are many solutions, print any of them.

如果没有最短路,输出-1,反之输出最短路径,如果存在多种情况,输出其中一条即可。

Examples

input

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

output

1 4 3 5

input

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

output

1 4 3 5

解题思路:

本题和上一篇其实比较相似,采用了SPFA算法,注意图G是双向的。

代码如下:C++

#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

vector<vector<pair<int, long long>>> graph;
vector<long long> dist;
vector<int> parent, ans;
vector<bool> visited;
deque<int> q;
int n, m, a, b, c;

#define pc(x) putchar(x)
#define gc() getchar()

inline void writeInt(int n) {
    int N = n, rev, count = 0;
    rev = N;
    if (N == 0) {
        pc('0');
        pc('\n');
        return;
    }
    while ((rev % 10) == 0) {
        count++;
        rev /= 10;
    }
    rev = 0;
    while (N != 0) {
        rev = (rev << 3) + (rev << 1) + N % 10;
        N /= 10;
    }
    while (rev != 0) {
        pc(rev % 10 + '0');
        rev /= 10;
    }
    while (count--)
        pc('0');
    pc(' ');
}

inline int FAST_IO() {
    char ch;
    int val = 0;
    ch = gc();
    while (ch == '\n' || ch == ' ')
        ch = gc();
    val = 0;
    while (ch >= '0' && ch <= '9') {
        val = (val * 10) + (ch - '0');
        ch = gc();
    }
    return val;
}

int main() {
    // 输入n和m
    n = FAST_IO();
    m = FAST_IO();

    //
    graph.resize(n + 5);

    while (m--) {
        a = FAST_IO();
        b = FAST_IO();
        c = FAST_IO();
        // 双向输入边
        graph[a].push_back(make_pair(b, c));
        graph[b].push_back(make_pair(a, c));
    }

    dist.resize(n + 5, 1e16);
    parent.resize(n + 5, -1);
    visited.resize(n + 5);
    // 从节点1开始
    dist[1] = 0;
    q.push_back(1);

    while (!q.empty()) {
        // 取出节点
        int v = q.front();
        visited[v] = true;
        q.pop_front();

        // 遍历相邻的边
        for (size_t i = 0; i < graph[v].size(); ++i) {
            int to = graph[v][i].first;
            int len = graph[v][i].second;

            // 更新d值
            if (dist[to] > dist[v] + len) {
                dist[to] = dist[v] + len;
                // 记录路径
                parent[to] = v;

                //spfa算法,如果没有访问过,就放到前面,优先遍历
                if (!visited[to])
                    q.push_front(to);
                else
                    q.push_back(to);

                visited[to] = true;
            }
        }
    }

    if (dist[n] < 1e16) {
        for (int i = n; i != -1; i = parent[i])
            ans.push_back(i);
        for (int i = ans.size() - 1; i > -1; --i)
            writeInt(ans[i]);
    } else
        printf("-1");

    return 0;
}

简单看完SPFA算法,可以再来了解一下Dijsktra算法对于负权的问题。

Dijsktra算法处理负权?

我们看看下面这张图:

负权图

算法刚开始执行时,将1添加到集合中标记已访问,之后选出从1到所有节点中的最短的d,于是把3加入集合中标记已访问,之后3不能在更新了,而显然,1与3之间最短路径权值为1(1-2-3),发生错误。

好啦,大概讲这些,可以思考一下:Dijkstra算法如何处理负权?

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:dansen

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • CodeForces 982F:The Meeting Place Cannot Be Changed(有向图)

    Petr is a detective in Braginsk. Somebody stole a huge amount of money from a ba...

    ACM算法日常
  • Planning mobile robot on Tree (EASY Version)(UVA12569,状态压缩)

    题目链接:https://vjudge.net/problem/UVA-12569

    ACM算法日常
  • 流问题Flow Problem(网络最大流)- HDU 3549

    网络最大流问题属于算法 里面较难的问题,因为牵涉的概念比较多,这一篇可能需要你花比较多的时间去理解,除了看这个,最好能多参考别的书籍或者文章进行...

    ACM算法日常
  • HELP! I’m an Object Factory!

    It has been a week since my last post, I’ve been coding on ePortal WYSIWYG ASP.N...

    张善友
  • 1269 匈牙利游戏 2012年CCC加拿大高中生信息学奥赛

    1269 匈牙利游戏 2012年CCC加拿大高中生信息学奥赛 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond...

    attack
  • DNSPod十问Matt Overman:二维码真的代替域名了吗?

    ? 问答时间:2020年6月24日 嘉宾简介: Matt Overman(SVP):Donuts注册局高级副总裁,Matt负责领导域名货币化和高级域名市场。曾...

    腾讯云DNSPod团队
  • python 脚本生成为可执行文件

    你会发现dist下面只有一个可执行文件,这个单文件就可以发布了,可以运行在你正在使用的操作系统类似的系统的下面。

    Devops海洋的渔夫
  • 创建自己的Code Snippets在VSCode中

    1. Go to Code → Preferences → User Snippets

    前端知否
  • 玩转RNA-seq数据也可以不需要linux ?

    Hepatocytes direct the formation of a pro-metastatic niche in the liver. Nature ...

    生信技能树
  • MySQL主从复制

    修改mysql配置文件,不同的系统my.cnf路径不同(CentOS中位于/etc/my.cnf)

    十毛

扫码关注云+社区

领取腾讯云代金券