16分2WA3TLE求条

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

zky2023_sz @ 2024-09-16 16:40:00

用的CF20C(Dijkstra?)改的

#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
vector<pair<int,ll> >node[N];
priority_queue<pair<ll,int> >q;
deque<ll>ans;
ll dis[N],vis[N],path[N];
int n,m,s;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>s;
    while(m--){
        int u,v,w;
        cin>>v>>u>>w;
        node[v].push_back(make_pair(u,w));
        node[u].push_back(make_pair(v,w));
    }

    q.push(make_pair(0,s));
    memset(dis,0x7f,sizeof dis);
    dis[1]=0;
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(vis[u]==1){
            continue;
        }
        else{
            vis[u]==1;
            for(int i=0;i<node[u].size();i++){
                if(dis[node[u][i].first]>dis[u]+node[u][i].second){
                    dis[node[u][i].first]=dis[u]+node[u][i].second;
                    q.push(make_pair(-dis[node[u][i].first],node[u][i].first));
                }
            }
        }       
    }
    if(dis[n]==0x7f7f7f7f7f7f7f7f){
        cout<<-1;
        return 0;
    }
    for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
    return 0;
}

|