为什么用long long 还是90分?求助!
查看原帖
为什么用long long 还是90分?求助!
457002
szhl0803楼主2022/7/10 11:57

这份代码跑标准版还是100分

//P4779 
#include <bits/stdc++.h>
#define N 100005

using namespace std;

struct node{
	vector<int>to;
	vector<int>far;
}p[N];

struct pa{
	int dis,now;
	bool operator <( const pa &x )const
    {
        return x.dis < dis;
    }
};

int n,m,s;

long long  dis[N];
bool vis[N];

void dijkstra()
{
	memset(dis,0x3f,sizeof(dis));
	dis[s] = 0;
	priority_queue<pa> q;
	q.push((pa){0,s});
	while(!q.empty())
	{
		pa nn = q.top();
		int now = nn.now;
		q.pop();
		if(vis[now])continue;
		vis[now] = 1;
		int sz = p[now].far.size();
		for(int i = 0;i<sz;i++)
		{
			int to = p[now].to[i];
			int far = p[now].far[i];
			if(dis[to] > dis[now] + far)
			{
				dis[to] = dis[now] + far;
				if(!vis[to])
				{
					q.push((pa) {dis[to],to});
				}
			}
		}
	}
}

int main()
{
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		p[u].to.push_back(v);
		p[u].far.push_back(w);
	}
	dijkstra();
	for(int i=1;i<=n;i++)
	printf("%lld ",dis[i]);
	return 0;
} 
2022/7/10 11:57
加载中...