64分,#1#5TLE,求助大佬。
查看原帖
64分,#1#5TLE,求助大佬。
148552
我很低调楼主2020/8/31 21:03

vector做的,就是领接表而已。加堆优化

#include<bits/stdc++.h>
#define ll register long long
#define R register
#define mod 20070707
#define maxs 0x3f3f3f3f

using namespace std;
struct node{long long v,w;};
vector<node>edge[100005];
priority_queue<pair<long long,long long> > Q;
long long dis[100005]={0};
bool vis[100005]={0};
int main(){//freopen(".in","r",stdin);freopen(".out","w",stdout);
	ll n,m,s;
	ll u,v,w;
	scanf("%lld%lld%lld",&n,&m,&s);
	for(ll i=1;i<=m;i++){
		scanf("%lld%lld%lld",&u,&v,&w),edge[u].push_back((node){v,w});
	}
	for(ll i=1;i<=n;i++)dis[i]=2147483647;dis[s]=0;
	Q.push(make_pair(s,0));
	while(!Q.empty()){
		pair<int,int> x=Q.top();Q.pop();
		u=x.first,w=x.second;
		if(dis[u]<w)continue;
		for(ll i=0;i<edge[u].size();i++){
			v=edge[u][i].v;
			if(dis[v]>dis[u]+edge[u][i].w){
				dis[v]=dis[u]+edge[u][i].w;
				Q.push(make_pair(v,dis[v]));
			}
		}
	}
	for(ll i=1;i<=n;i++)printf("%lld ",dis[i]);
	return 0;
}

2020/8/31 21:03
加载中...