U505391 Obsidian Pinnacle 题解

H_MC · 2024-11-20 13:00:52 · 题解

传送门

这是一道 最短路 的板子题，也没什么特别难的，直接上代码。

// 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;                                                                                                          
}