345wa,求助

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

Botter @ 2024-04-12 19:44:02

#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <string>
#define inf 0x3f3f3f
//#define int long long

using namespace std;
struct node{
    long v,w;
};
vector<node>e[2*100005+5];
long d[2*100005+5];
bool vis[2*100005+5];
long e_,v,w,s,n,m;
priority_queue<pair<long,long>>q;
void dij(long s){
    for (long i = 0 ; i<= n ; i++) {
        d[i] = inf;
    }
    d[s] = 0;
    q.push({0,s});
    while(q.size()){
        auto t = q.top() ; q.pop();
        long u = t.second;
        if (vis[u]) continue;
        vis[u] = 1;
        for (node ed : e[u]){
            long v = ed.v , w = ed.w;
            if (d[v] > d[u]+w){
                d[v] = d[u]+w;
                q.push({-d[v],v});
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> s;
    for (long i = 1 ; i <= m ; i++){
        cin >> e_ >> v >> w;
        e[e_].push_back({v,w});
    }
    dij(s);
    for (long i = 1 ; i <= n ; i++){
        cout << d[i] << " ";
    }
    return 0;
}

by Botter @ 2024-04-12 19:48:03

开了long long还是wa了


by chengcheng567 @ 2024-04-12 19:48:45

不是,哥们,你inf开小了


by chengcheng567 @ 2024-04-12 19:49:56

把inf开成2e9


by chengcheng567 @ 2024-04-12 19:50:26

这题有保证sigma w<=1e9所以不用long long


by chengcheng567 @ 2024-04-12 19:51:25

你现在的inf是4144959只有4e6左右


by Botter @ 2024-04-13 23:19:58

@chengcheng567 A了,谢谢大佬


|