U505391 Obsidian Pinnacle 题解

// dijkstra 版
#include<bits\stdc++.h>                                                                                                          
#include<Windows.h>                                                                                                          
#define LL long long                                                                                                          
#define pii pair<int,int>                                                                                                          
#define mk(x,y) make_pair(x,y)                                                                                                          
#define Fcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int y1;//一大堆没什么用的define                                                                                                           
using namespace std;                                                                                                          
const int N=1e5+100;                                                                                                          
const int inf=0x3f3f3f3f;                                                                                                          
bool vis[N];                                                                                                          
int dis[N],n,m,s;                                                                                                          
vector<pii > G[N];                                                                                                          
priority_queue<pii > q;//使用优先队列维护                                                                                                           
int main()                                                                                                          
{                                                                                                          
	Fcin;                                                                                                          
	cin>>n>>m;                                                                                                          
	while(m--)                                                                                                          
	{                                                                                                          
		int u,v,w;                                                                                                          
		cin>>u>>v>>w;                                                                                                          
		G[u].push_back(mk(v,w));                                                                                                          
		G[v].push_back(mk(u,w));//建图                                                                                                           
	}                                                                                                          
	cin>>s;                                                                                                          
	memest(dis,inf,sizeof dis);//初始化                                                                                                           
	dis[s]=0,q.push(mk(dis[s],s));                                                                                                          
	while(!q.empty())                                                                                                          
	{                                                                                                          
		int t=q.top().second;                                                                                                          
		q.pop();                                                                                                          
		if(vis[t]) continue;                                                                                                          
		vis[t]=0;                                                                                                          
		for(int i=0;i<G[t].size();i++)//每个与t连通的点                                                                                                           
		{                                                                                                          
			int to=G[t][i].first,weg=G[t][i].second;                                                                                                          
			if(vis[to]) continue;                                                                                                          
			if(dis[to]>dis[t]+weg)//如果原来到to的路程比先到t再去to还远                                                                                                           
			{                                                                                                          
				dis[to]=dis[t]+weg;//更新目前最短的路程                                                                                                           
				q.push(mk(-dis[to],to));                                                                                                          
			}                                                                                                          
		}                                                                                                          
	}                                                                                                          
	for(int i=1;i<=n;i++)                                                                                                          
		cout<<dis[i]<<" ";//输出                                                                                                           
	return 0;                                                                                                          
}                                                                                                          

// spfa 版                                                                                                          
#include<bits\stdc++.h>                                                                                                      
#include<Windows.h>                                                                                                      
#define LL long long                                                                                                          
#define Fcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int y1;                                                                                                          
using namespace std;                                                                                                          
const int N=1e5+100;                                                                                                          
const int inf=0x3f3f3f3f;                                                                                                          
struct node{int to,val;};//结构体                                                                                                           
queue<int> q;                                                                                                          
vector<node> G[N];//动态数组存图                                                                                                           
int n,m,s,dis[N];                                                                                                           
bool vis[N];                                                                                                          
int main()                                                                                                          
{                                                                                                          
	Fcin;                                                                                                          
	cin>>n>>m;                                                                                                          
	while(m--)                                                                                                          
	{                                                                                                          
		int u,v,w;                                                                                                          
		cin>>u>>v>>w;                                                                                                          
		G[u].push_back({v,w});                                                                                                          
		G[v].push_back({u,w});                                                                                                          
	}                                                                                                          
	cin>>s;                                                                                                          
	memest(dis,inf,sizeof dis);                                                                                                          
	dis[s]=0,vis[s]=1,q.push(s);                                                                                                          
	while(!q.empty())                                                                                                          
	{                                                                                                          
		int t=q.front();                                                                                                          
		q.pop();                                                                                                          
		vis[t]=0;                                                                                                          
		for(int i=0;i<G[t].size();i++)                                                                                                          
		{                                                                                                          
			int x=G[t][i].to;                                                                                                          
			if(dis[x]>dis[t]+G[t][i].val)//一样的判断                                                                                                           
			{                                                                                                          
				dis[x]=dis[t]+G[t][i].val;                                                                                                          
				if(!vis[x])//防止重复                                                                                                           
				{                                                                                                          
					vis[x]=1;                                                                                                          
					q.push(x);                                                                                                          
				}                                                                                                          
			}                                                                                                          
		}                                                                                                          
	}                                                                                                          
	for(int i=1;i<=n;i++) cout<<dis[i]<<" ";                                                                                                          
	return 0;                                                                                                          
}