4 条题解

  • -29
    @ 2023-8-16 14:43:30
    #include<bits/stdc++.h>
    using namespace std;
    #define PI pair<int,int>
    struct node{
    	int v;
    	int w;
    };
    int n,m,u,v,w,s;
    vector<node> a[100005];
    int dis[100005],h[100005];
    priority_queue<PI,vector<PI>,greater<PI> > q;
    int main(){
    	cin>>n>>m>>s;
    	for(int i=1;i<=m;i++){
    		cin>>u>>v>>w;
    		a[u].push_back(node{v,w});
    	}
    	memset(dis,0x3f,sizeof(dis));
    	q.push(make_pair(0,s));
    	while(!q.empty()){
    		u=q.top().second;
    		w=q.top().first;
    		q.pop();
    		if(h[u])continue;
    		h[u]=1;
    		for(int i=0;i<a[u].size();i++){
    			v=a[u][i].v;
    			w=a[u][i].w;
    			if(dis[v]>dis[u]+w){
    				dis[v]=dis[u]+w;
    				q.push(make_pair(dis[v],v));
    			}
    		}
    	}
    	for(int i=1;i<=n;i++){
    		cout<<dis[i]<<" ";
    	}
    	return 0;
    }
    

    信息

    ID
    475
    时间
    1000ms
    内存
    512MiB
    难度
    3
    标签
    递交数
    520
    已通过
    119
    上传者