算法训练 最短路
时间限制：1.0s 内存限制：256.0MB
问题描述
给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。
输入格式
第一行两个整数n, m。
接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。
输出格式
共n-1行，第i行表示1号点到i+1号点的最短路。
样例输入
3 3
1 2 -1
2 3 -1
3 1 2
1 2 -1
2 3 -1
3 1 2
样例输出
-1
-2
-2
数据规模与约定
对于10%的数据，n = 2，m = 2。
对于30%的数据，n <= 5，m <= 10。
对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。
Bellman—ford算法
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX = 0x3f3f3f3f;
int v[500005], u[500005]; //起点，终点
int w[500005]; //权值
int n, m; //顶点数，边数
int d[20005]; //路径数组
void bellman(int s){
memset(d, MAX, sizeof(d));
d[s] = 0; //必须初始化这个
int flag = 1;
for(int k = 0; k < n - 1; k++){
flag = 1;
for(int i = 0; i < m; i++){ //遍历每一条边
if(d[u[i]] > d[v[i]] + w[i]){//如果这条边的终点的d[]值小于起始点的d[]值加上这条边的权值，则更新d
d[u[i]] = d[v[i]] + w[i];
flag = 0;
}
}
if(flag){
break;
}
}
}
int main(){
int ss;
while(scanf("%d%d", &n, &m) == 2){
for(int i = 0; i < m; i++){
scanf("%d%d%d", &v[i], &u[i], &w[i]);
}
int s, e;
// scanf("%d%d", &s, &e);
// bellman(s);
// if(d[e] < MAX){
// printf("%d
", d[e]);
// }
// else{
// printf("-1
");
// }
bellman(1);
for(int i = 2; i <= n; i++){
printf("%d
", d[i]);
}
}
return 0;
}
spfa算法：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
const int MAX = 0x3f3f3f3f;
vector <int>v1[20005]; //v1[i]表示i到的终点
vector <int>v2[20005]; //v2[i]表示i和v1[i]的边的权值
int visit[20005]; //表示是否已经在队列里面
int d[20005];
int n, m, ss;
void spfa(int ss){
memset(d, 0x3f, sizeof(d));
d[ss] = 0;
queue <int>mq;
mq.push(ss);
visit[ss] = 1;
while(!mq.empty()){
int x = mq.front();
mq.pop();
visit[x] = 0;
for(int i = 0; i < v1[x].size(); i++){
int v = v1[x][i];
int len = v2[x][i];
if(d[v] > d[x] + len){
d[v] = d[x] + len;
if(visit[v] == 0){ //这个在上一个if里面，只有别更新了，才有可能影响其他点，才放入队列
mq.push(v);
visit[v] = 1;
}
}
}
}
}
int main(){
while(cin >> n >> m){
memset(visit, 0, sizeof(visit));
memset(v1, 0, sizeof(v1));
memset(v2, 0, sizeof(v2));
int x, y, z;
for(int i = 0; i < m; i++){
cin >> x >> y >> z;
// if(z < v2[x][y]){ //两个点多条路，去最短的
v2[x].push_back(z); //压入权值
v1[x].push_back(y); //压入x的另一个顶点
// }
}
int end;
spfa(1);
// for(int i = 1; i <= n; i++){
// if(d[i] < MAX){
// cout << d[i] << " ";
// }
// else{
// cout << 2147483647 << " ";
// }
// }
for(int i = 2; i <= n; i++){
printf("%d
", d[i]);
}
}
return 0;
}