2361: 【例】【入门】有负权边的最短路
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。
输入
第一行两个整数n, m。
接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。
对于10%的数据，n = 2，m = 2。
对于30%的数据，n <= 5，m <= 10。
对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。
输出
共n-1行，第i行表示1号点到i+1号点的最短路。
样例输入 复制
3 3
1 2 -1
2 3 -1
3 1 2样例输出 复制
-1
-2提示
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef long long ll;
const int MAXN = 20005;
const ll INF = 1e18;
vector<pair<int,int>> g[MAXN];
ll dist[MAXN];
bool inqueue[MAXN];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
cin >> n >> m;
for(int i=1;i<=m;i++)
{
int u,v,l;
cin >> u >> v >> l;
g.emplace_back(v,l);
}
// SPFA初始化
for(int i=1;i<=n;i++) dist[i]=INF;
queue<int> q;
dist[1]=0;
q.push(1);
inqueue[1]=true;
while(!q.empty())
{
int u = q.front();
q.pop();
inqueue=false;
for(auto &edge : g)
{
int v = edge.first;
int w = edge.second;
if(dist[v] > dist + w)
{
dist[v] = dist + w;
if(!inqueue[v])
{
q.push(v);
inqueue[v]=true;
}
}
}
}
// 输出：1到2，1到3，……，1到n
for(int i=2;i<=n;i++)
{
cout << dist[i] << '\n';
}
return 0;
}