给定一个 n 个点 m 条边的有向图, 图中可能存在重边和自环, 边权可能为负数.
请你求出 1 号点到 n 号点的最短距离, 如果无法从 1 号点走到 n 号点, 则输出 impossible.
数据保证不存在负权回路.
输入格式
第一行包含整数 n 和 m.
接下来 m 行每行包含三个整数 x,y,z, 表示存在一条从点 x 到点 y 的有向边, 边长为 z.
输出格式
输出一个整数, 表示 1 号点到 n 号点的最短距离.
如果路径不存在, 则输出 "impossible".
数据范围
1≤n,m≤1051≤n,m≤105,
图中涉及边长绝对值均不超过 10000.
输入样例:
- 3 3
- 1 2 5
- 2 3 -3
- 1 3 4
输出样例:
2
对 bellman_ford 优化
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- #include <queue>
- using namespace std;
- typedef pair<int, int> PII;
- const int N = 1e5 + 10;
- int n, m;
- int h[N], w[N], e[N], ne[N], idx;
- int dist[N];
- bool st[N];
- void add(int a, int b, int c)
- {
- e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
- }
- int spfa()
- {
- memset(dist,0x3f,sizeof dist);
- dist[1] = 0;
- // 定义队列存储所有待更新的点
- queue<int> q;
- q.push(1);//1 号点放入队列
- st[1] = true;// 表示当前这个点是不是在队列当中, 防止队列当中存储重复的点
- while(q.size()){// 队列不空
- int t = q.front();
- q.pop();
- st[t] = false;
- // 更新 t 的所有的邻边
- for(int i = h[t];i != -1;i = ne[i]){
- int j = e[i];
- if(dist[j]> dist[t] + w[i])
- {
- dist[j] = dist[t] + w[i];
- if(!st[t])
- {
- q.push(j);
- st[j] = true;
- }
- }
- }
- }
- if(dist[n] == 0x3f3f3f3f) return -1;
- else return dist[n];
- }
- int main()
- {
- scanf("%d%d", &n, &m);
- memset(h, -1, sizeof h);
- while (m -- )
- {
- int a, b, c;
- scanf("%d%d%d", &a, &b, &c);
- add(a, b, c);
- }
- int t = spfa();
- if(t == -1) cout << "impossible";
- else
- cout << spfa() << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3282038.html