牛客14369之最短路(SPFA模板)

vampire 2020年10月05日 54次浏览

链接:https://ac.nowcoder.com/acm/problem/14369
来源:牛客网

对于本文中涉及算法原理可自行百度,或者参考我的其他博客,在计算机基础分类下

  • 题目描述

简单暴力的题目要求:
给定一个有n个顶点(从1到n编号),m条边的有向图(其中某些边权可能为 负,但保证没有负环)。请你计算从1号点到其他点的最短路。

  • 输入描述:

第一行两个整数n, m。
接下来的m行,每行有三个整数u, v, l,表示u到v有一条长度为l的边。

  • 输出描述:

共n-1行,第i行表示1号点到i+1号点的最短路。

  • 示例1
    • 输入
    	3 3
    	1 2 -1
    	2 3 -1
    	3 1 2
    
    • 输出
    	-1
    	-2
    
  • 说明

对于10%的数据,n = 2,m = 2。
对于30%的数据,n <= 5,m <= 10。
对于100%的数据,1 <= n <= 20000,1 <= m <= 200000,-10000 <= l <= 10000,保证从任意顶点都能到达其他所有顶点。

  • 题目解析

本题要求1到任意点的最短路,即任意两点之间的最短路径问题
注意有负权
对于这个问题我们可以使用Floyd算法或者SPFA算法
题目中说明不会存在负环
观察数据量要求,Floyd算法不适用,所以这道题是一个SPFA算法的模板题
对于SPFA是对于BFS算法的优化,加入了动态更新。

  • 代码展示
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 2e4+10;
const int M = 2e5+10;
const int inf = 0x3f3f3f3f;
struct edge{
    int v, w, next;
    edge(){}
    edge(int _v, int _w, int _next){
        v = _v;
        w = _w;
        next = _next;
    }
}e[M];
int head[N], size;
void init(){
    memset(head, -1, sizeof(head));
    size = 0;
}
void insert(int u, int v, int w){
    e[size] = edge(v, w, head[u]);
    head[u] = size++;
}
void insert2 (int u, int v, int w){
    insert(u, v, w);
    insert(v, u, w);
}
int n, m;
int dis[N];
bool vis[N];
void spfa(int u){
    memset(vis, false, sizeof(vis));
    vis[u] = true;
    memset(dis, inf, sizeof(dis));
    dis[u] = 0;
    queue<int> q;
    q.push(u);
    while(!q.empty()){
        u = q.front();
        q.pop();
        vis[u] = false;
        for (int j=head[u]; ~j; j=e[j].next){
            int v = e[j].v;
            int w = e[j].w;
            if(dis[v] > dis[u]+w){
                dis[v] = dis[u]+w;
                if(!vis[v]){
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}
int main(){
    init();
    cin >> n >> m;
    int a, b, c;
    while(m--){
        cin >> a >> b >> c;
        insert(a, b, c);
    }
    spfa(1);
    for (int i=2; i<=n; i++){
        cout << dis[i] << endl;
    }
    return 0;
}