T了一个点……

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

wangxinyu777 @ 2023-07-23 23:17:42

开了O2,一个点1.02s=>TLE(悲……),求大佬们看看

#include <bits/stdc++.h>
using namespace std;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> nodes; 
const int N = 1e5+5;
int n,m,start;
vector<pair<int,int>> edge[N];
int dist[N];
inline void dij() {
    for(register int i = 1;i <= n;++i) dist[i] = 2147483647;
    nodes.push({0,start});
    dist[start] = 0;
    while(!nodes.empty()) {
        pair<int,int> now = nodes.top();
        nodes.pop();
        for(auto nxt : edge[now.second]) {
            if(dist[nxt.first] > dist[now.second]+nxt.second) {
                dist[nxt.first] = dist[now.second]+nxt.second;
                nodes.push({dist[nxt.first],nxt.first});
            }
        }
    }
}
inline void read(int &x)
{
    int f(1);
    x=0;
    char s=getchar();
    while(s<'0'||s>'9')
    {
        if(s=='-')
            f=-1;
        s=getchar();
    }
    while(s>='0'&&s<='9')
    {
        x=x*10+s-'0';
        s=getchar();
    }
    x*=f;
}
void print(int x) {
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10^48);
}
int main() {
    read(n),read(m),read(start);
    for(register int i = 1;i <= m;++i) {
        int u,v,w;
        read(u),read(v),read(w);
        edge[u].push_back({v,w});
    }
    dij();
    for(register int i = 1;i <= n;++i) {
        print(dist[i]);
        putchar(' ');
    }
    putchar('\n');
    return 0;
}

|