P2984 [USACO10FEB] Chocolate Giving S

· · 题解

P2984 [USACO10FEB] Chocolate Giving S

题目理解：

本题就是给你一个无向图，求从其中一个点到另一个点（其中必经过1号点）的最短路。我们只需要转换一下，也就是求从一号点到任意一点的最短路，询问时只需要输出一号点到那两个点的最短路和即可。用Dijkstra跑一遍即可

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=50010;
struct edge{
    int v,w;
};
struct node{
    int dis,u;
    bool operator>(const node& a)const{return dis>a.dis;}
};
int dis[N],vis[N];
priority_queue<node,vector<node>,greater<node>>q;
vector<edge>e[N];
void dijkstra(){
    memset(dis,0x3f,sizeof(dis));
    q.push({0,1});
    dis[1]=0;
    while(!q.empty()){
        int u=q.top().u;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(auto ed:e[u]){
            int w=ed.w,v=ed.v;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push({dis[v],v});
            }
        }
    }
}
int main(){
    int n,m,b;
    cin>>n>>m>>b;
    for(int i=1;i<=m;i++){
        int u,v,w; 
        cin>>u>>v>>w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    dijkstra(); 
    for(int i=1;i<=b;i++){
        int x,y;
        cin>>x>>y;
        cout<<dis[x]+dis[y]<<endl;
    }
}

dijkstra原理讲解