C++ 代码

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int n, m;
const int N = 1e5 + 10;
using PII = pair<int, int>;
int dist[N], vis[N];
vector<vector<PII>> d;

int spfa(int start, int end){
    memset(dist, 0x3f, sizeof dist);
    dist[start] = 0;

    queue<int> q;
    q.push(start);
    vis[start] = 1;

    while(!q.empty()){
        auto t = q.front();
        q.pop();
        vis[t] = 0;

        for(auto i : d[t]){
            int j = i.first, u = i.second;
            if(dist[j] > dist[t] + u){
                dist[j] = dist[t] + u;
                if(!vis[j]) q.push(j);
                vis[j] = 1;
            }
        }
    }
    if(dist[end] > 0x3f3f3f3f / 2) return -1;
    return dist[end];
}

int main()
{
    cin >> n >> m;
    d.resize(n + 1);
    while(m --){
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        d[a].emplace_back(b, w);
    }

    int ret = spfa(1, n);
    if(ret == -1)  puts("impossible");
    else cout << ret << endl;

    return 0;
}