# 最短路专题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.

## 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.

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.

## Examples

### input

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

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

1 4 3 5

## 代码如下：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;
}
```

## Dijsktra算法处理负权?

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...

• ### Planning mobile robot on Tree (EASY Version)（UVA12569，状态压缩)

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

• ### 流问题Flow Problem（网络最大流）- HDU 3549

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

• ### 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...

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

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

• ### python 脚本生成为可执行文件

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

• ### 创建自己的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）