32分求调

P4779 【模板】单源最短路径(标准版)

thrniseven @ 2024-09-21 21:36:39


#include<bits/stdc++.h>
#define pil pair<int,int>
using namespace std;
const long long N = 1e5;
const long long M = 2e5;
long long head[N];
long long val[M];
long long nex[M];
long long to[M];
long long cnt = 1;
long long dist[N];
bool visit[N];
long long ansct = 0;
void built(long long u, long long v, long long w) {
    nex[cnt] = head[u];
    to[cnt] = v;
    val[cnt] = w;
    head[u] = cnt++;
}
int main() {
    memset(dist, 127, sizeof(dist));
    long long n, m, s;
    cin >> n >> m >> s;
    for (long long i = 0; i < m; i++) {
        long long v, u, w;
        cin >> u >> v >> w;
        built(u, v, w);
    }
    priority_queue<pil, vector<pil>, greater<pil>>q;
    q.push({ 0,s });
    dist[s] = 0;
    while (!q.empty()) {
        long long dis = q.top().first;
        long long cur = q.top().second;
        q.pop();
        if (visit[cur]) {
            continue;
        }
        else {
            visit[cur] = 1;
        }

        for (long long i = head[cur]; i; i = nex[i]) {
            long long v = to[i];
            long long cost = val[i];
            if (!visit[v] && dist[cur] + cost < dist[v]) {
                dist[v] = dist[cur] + cost;
                q.push({ dist[cur] + cost,v });
            }

        }

    }
    for (long long i = 0; i < n; i++) {
        cout << dist[i + 1] << " ";
    }
}

by thrniseven @ 2024-09-21 22:21:38

这个节点数n怎么是顶满了开的呜呜呜,我改成N = 1e5+1 过了


|