题解 P1828 【香甜的黄油 Sweet Butter】

· · 题解

香甜的奶油

这个题似乎没有vector的dij，我来补一个

2019.08.03补充之前挂了的图片QwQ

首先，坦白讲，我先把数据构了一个图看看样例中是一个菱形的图，像这样

如果泥萌想做更多图的话，戳进去吧
那么就很显然了，从3->4，边权为5，从2->4，边权为3，所以3+5=8，样例输出了8.

so，我们需要让他跑一个最短路，pos数组记录当前点的位置，deep数组记录当前点的深度

如果要学习堆优化的dij，看一下这个blog吧,虽然不是我的，但也是一个dalao的题解

详细见代码注释(莫抄) 

#include <bits/stdc++.h>
using namespace std;

struct point{//记录一个点的两项性质，to和val
    int to,val;
};

int n,p,c;//见题意
int pos[810],deep[810];//见上面解释
int u,v,w;//输入的三个数
int ans=0x7fffffff;//求最小值，ans初始化为最大值
vector<point> side[810];//堆优化+存图

inline void dijkstra(int x){//最短路开始啦！
    queue<int> q;
    q.push(x);
    deep[x]=0;
    while(!q.empty()){
        int to=q.front();
        q.pop();
        for(int i=0;i<side[to].size();i++){
            point t=side[to][i];
            if(deep[t.to]>deep[to]+t.val){//比它小就更新答案
                deep[t.to]=deep[to]+t.val;
                q.push(t.to);//循环的队列
            }
        }
    }
}

int main(){
    cin>>n>>p>>c;//输入
    for(int i=1;i<=n;i++)   cin>>pos[i];//输入奶牛们的位置
    while(c--){
        cin>>u>>v>>w;//输入
        point t;//定义一个需要更新位置的结构体
        t.to=v;
        t.val=w;
        side[u].push_back(t);//两次建图
        t.to=u;
        side[v].push_back(t);
    }
    for(int i=1;i<=p;i++){
        memset(deep,0x3f,sizeof(deep));//每次要更新深度
        dijkstra(i);//跑最短路
        int sum=0;
        for(int i=1;i<=n;i++)
            sum+=deep[pos[i]];
        ans=min(ans,sum);//取最小值
    }
    while(1)
    cout<<ans<<'\n';//输出答案即可
    return 0;//OK结束
}

码字不易，求通过，蟹蟹啦