P3371 【模板】单源最短路径（弱化版） · znzryb

## 题目大意

给定一个有向带权图（$N$ 点 $M$ 边），求从源点 $s$ 到所有其他点的最短路径长度。如果无法到达则输出特定值（如 $2^{31} - 1$）。数据范围较小，允许 $O(NM)$ 算法。

## AC代码

[https://www.luogu.com.cn/problem/P3371](https://www.luogu.com.cn/problem/P3371)

```cpp
#include <iostream>
#include <vector>
#include <deque>
#include <cmath>
#define rep(i,n) for(int i=1;i<=(n);i++)
using namespace std;
typedef long long ll;
const ll N=1e4+10,INF=1e18+7;
vector<pair<ll,ll> > g[N];
ll n,m,u,v,w,dis[N],s;
deque<pair<ll,ll> > q;
void dijkstra() {
    dis[s]=0;
    q.push_back(make_pair(s,0)); // curr_node curr_dis
    while(!q.empty()) {
        ll cn=q.front().first,cdis=q.front().second;
        for(int i=0;i<g[cn].size();i++) {
            ll ni=g[cn][i].first; ll wi=g[cn][i].second;
            if(cdis+wi<dis[ni]) {
                dis[ni]=cdis+wi;
                q.push_back(make_pair(ni,cdis+wi));
            }
        }
        q.pop_front();
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>s;
    rep(i,n) {
        dis[i]=INF;
    }
    rep(_,m) {
        cin>>u>>v>>w;
        g[u].push_back(make_pair(v,w));
    }
    dijkstra();
    ll forOut=pow(2,31)-1;
    rep(i,n) {
        if(dis[i]!=INF)
            cout<<dis[i]<<" ";
        else
            cout<<forOut<<" ";
    }
    cout<<endl;
    return 0;
}
// AC https://www.luogu.com.cn/record/181870206
```

第一次提交就基本AC了，没啥心路历程