tr

第一份代码使用了bool operator但是WA #1 & #5

而第二份代码成功AC

第一份：

/*
2018年7月19日,某位同学在 NOI D1T1归程一题里非常熟练地使用了一个广为人知的算法求最短路。
然后呢？
100 →60；
Ag →Cu
最终,他因此没能与理想的大学达成契约。
大K 衷心祝愿大家不再重蹈覆辙。
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
const int INF=0x3f3f3f3f3f3f3f3f;

int n,m,s,dis[N];//dis数组表示起点到某点的最短路大小
bool vis[N];

struct Edge{
	int to,w,nxt;
}e[N*2];int tot,head[N];

inline void addedge(int u,int v,int w)//链式前向星存图。 
{e[++tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot;}

struct cmp{
	bool operator()(const int &x, const int &y) const{
		return dis[x]>dis[y];
	}//Priaority_queue 的 Compare 需要使用结构体的运算符重载完成，直接 bool cmp 是无法通过编译的。
};priority_queue<int,vector<int>,cmp> q;
void dijkstra(int o)
{
	memset(dis,0x3f,sizeof(dis));//初始化
	memset(vis,0,sizeof(vis));
	dis[o] = 0;
	q.push(o);
	while(!q.empty())
	{        
		int now=q.top();q.pop();
		if(vis[now]) continue;
		vis[now]=1;
		for(int i=head[now];i;i=e[i].nxt)
		{
			int to=e[i].to;
			if(dis[to]>dis[now]+e[i].w)
			{
				dis[to]=dis[now]+e[i].w;
				q.push(to);
			}
		}            
	}
}

signed main()
{
	cin>>n>>m>>s;
	for(int i=1,u,v,w;i<=m;++i)
	{
		cin>>u>>v>>w;addedge(u,v,w);
	}
	dijkstra(s);
	for(int i=1;i<=n;++i)
	{
		cout<<dis[i]<<" ";		
	}
	return 0;
}

第二份：

/*
2018年7月19日,某位同学在 NOI D1T1归程一题里非常熟练地使用了一个广为人知的算法求最短路。
然后呢？
100 →60；
Ag →Cu
最终,他因此没能与理想的大学达成契约。
大K 衷心祝愿大家不再重蹈覆辙。
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
const int INF=0x3f3f3f3f3f3f3f3f;

int n,m,s,dis[N];//dis数组表示起点到某点的最短路大小
bool vis[N];

struct Edge{
	int to,w,nxt;
}e[N*2];int tot,head[N];

inline void addedge(int u,int v,int w)//链式前向星存图。 
{e[++tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot;}

struct cmp{
	bool operator()(const int &x, const int &y) const{
		return dis[x]<dis[y];
	}//Priaority_queue 的 Compare 需要使用结构体的运算符重载完成，直接 bool cmp 是无法通过编译的。
};//priority_queue<int,vector<int>,cmp> q;
void dijkstra(int o)
{
	memset(dis,0x3f,sizeof(dis));//初始化
	memset(vis,0,sizeof(vis));
	priority_queue<pair<int,int> > q;
	dis[o] = 0;
	q.push({-dis[o], o});
	while(!q.empty())
	{        
		int now=q.top().second;q.pop();
		if(vis[now]) continue;
		vis[now]=1;
		for(int i=head[now];i;i=e[i].nxt)
		{
			int to=e[i].to;
			if(dis[to]>dis[now]+e[i].w)
			{
				dis[to]=dis[now]+e[i].w;
				q.push({-dis[to], to});
			}
		}            
	}
}

signed main()
{
	cin>>n>>m>>s;
	for(int i=1,u,v,w;i<=m;++i)
	{
		cin>>u>>v>>w;addedge(u,v,w);
	}
	dijkstra(s);
	for(int i=1;i<=n;++i)
	{
		cout<<dis[i]<<" ";		
	}
	return 0;
}