题解 P2984 【[USACO10FEB]Chocolate Giving S】

· · 题解

关于Floyd，它太慢了

关于spfa,它死了

关于dijkstra，还是用它吧

步入正题：

这道题，千万不要被题面所误导

题目大意：点u到点1的最短路+点1到点v的最短路

但是，您要是照着这个思路写代码的话，只能拿到50分，T了5个点

显然，这个做法不够优秀

进一步，我们发现，在第i头奶牛的行动中，肯定会经过1号点

所以，只要跑一边dijkstra就好了，把起点设为1

每当进行一次询问，就输出d[u]+d[v] （d[]记录最短距离）

//注释都在代码里了

上代码：（vector存图+dijkstra+堆优化）

//代码重在实用，不在华丽的操作 
#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,t,d[50010],ans;
//n个节点，m条边，t次询问，d[]存最短距离，ans为每次询问的答案 
struct edge
{
    int to,cost;
};
vector<edge>G[50010];//vector存图 
typedef pair<int,int>P;//定义一个pair类型的P（只是为了写起来简单一点） 
void dijkstra(int s)//s为起点，在这道题里就是1 
{
    priority_queue<P,vector<P>,greater<P> >q;
    //一个P类型（pair）类型的优先队列  
    for(int i=1;i<=n;i++) d[i]=1e9;//赋初值1e9 
    d[s]=0;//自己到自己的距离是0 
    q.push(P{0,s});//加入队列等待处理 
    while(!q.empty())
    {
        P p=q.top();//取队首 
        q.pop();
        //声明一下：p.first代表的是一个距离，而p.second代表的是一个点， 
        //Tell一个不为人知的秘密， 
        //若把p.first设为一个点，而把p.second设为一个距离，
        //程序的速度就没有第一个优秀（亲测） 
        int v=p.second;//也是为了写起来简便一点， 
        if(d[v]<p.first) continue;//如果已经是一个最短距离了，continue； 
        for(int i=0;i<G[v].size();i++)//循环点v连接的所有点 
        {
            edge e=G[v][i]; 
            if(d[e.to]>d[v]+e.cost)//松弛操作，贪心思想 
            {
                d[e.to]=d[v]+e.cost;//更新d[e.to]的值 
                q.push(P{d[e.to],e.to});//重新加入到队列等待处理 
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&t);
    while(m--)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        G[u].push_back(edge{v,w});//注意，这个图是一个无向图 
        G[v].push_back(edge{u,w});
    }
    dijkstra(1);
    //以1号点为起点进行dijkstra()，便可获得1号点到其它任意一点的最短距离 
    while(t--)
    {
        ans=0;
        int u,v;
        scanf("%d%d",&u,&v);
        ans=d[u]+d[v];//直接输出答案 
        printf("%d\n",ans);
    }
    return 0;//养成良好习惯 
}

这世界上不缺少什么水题，而是缺少发现水题的眼睛

看我写的这么认真，是否可以点个赞再走呢？