洛谷P1825
题目描述
Farmer John 发现了做出全威斯康辛州最甜的黄油的方法:糖。
把糖放在一片牧场上,他知道 NNN 只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。当然,他将付出额外的费用在奶牛上。
Farmer John 很狡猾。像以前的 Pavlov,他知道他可以训练这些奶牛,让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声,以至他可以在晚上挤奶。
Farmer John 知道每只奶牛都在各自喜欢的牧场(一个牧场不一定只有一头牛)。给出各头牛在的牧场和牧场间的路线,找出使所有牛到达的路程和最短的牧场(他将把糖放在那)。
输入格式
第一行包含三个整数 N,P,CN,P,CN,P,C,分别表示奶牛数、牧场数和牧场间道路数。
第二行到第 N+1N+1N+1 行,每行一个整数,其中第 iii 行的整数表示第 i−1i-1i−1 头奶牛所在的牧场号。
第 N+2N+2N+2 行到第 N+C+1N+C+1N+C+1 行,每行包含三个整数 A,B,DA,B,DA,B,D,表示牧场号为 AAA 和 BBB 的两个牧场之间有一条长度为 DDD 的双向道路相连。
输出格式
输出一行一个整数,表示奶牛必须行走的最小的距离和。
输入输出样例
输入 #13 4 5 2 3 4 1 2 1 1 3 5 2 3 7 2 4 3 3 4 5输出 #1
8
说明/提示
数据范围
对于所有数据,1≤N≤5001 \le N \le 5001≤N≤500,2≤P≤8002 \le P \le 8002≤P≤800,1≤A,B≤P1 \le A,B \le P1≤A,B≤P,1≤C≤14501 \le C \le 14501≤C≤1450,1≤D≤2551 \le D \le 2551≤D≤255。
样例解释
作图如下:
P2
P1 @--1--@ C1
|
|
5 7 3
|
| C3
C2 @--5--@
P3 P4
把糖放在4号牧场最优。
每个点都跑一下dijk即可,但是要堆优化,不然会爆炸
#include <bits/stdc++.h> using namespace std; const int N=1005; struct edge { int v, w; bool operator <(const edge &A) const { return w>A.w; } }; vector<edge> a[N]; int n, p, c, cow[N], u1, v1, w1; int dis[N], vis[N], sum=0, ans=INT_MAX, flag=0; priority_queue<edge> q; void dij(int s) { memset(dis, 63, sizeof dis); memset(vis, 0, sizeof vis); dis[s]=0, q.push({s, 0}); while (!q.empty()) { int u=q.top().v; q.pop(); if (vis[u]) continue; vis[u]=1; for (int i=0; i<a[u].size(); i++) { int v=a[u][i].v, w=a[u][i].w; if (!vis[v] && dis[v]>dis[u]+w) { dis[v]=dis[u]+w; q.push({v, dis[v]}); } } } } int main() { scanf("%d%d%d", &n, &p, &c); for (int i=1; i<=n; i++) scanf("%d", &cow[i]); for (int i=1; i<=c; i++) { scanf("%d%d%d", &u1, &v1, &w1); a[u1].push_back({v1, w1}); a[v1].push_back({u1, w1}); } for (int i=1; i<=p; i++) { sum=0, flag=0; dij(i); for (int j=1; j<=n; j++) { if (dis[cow[j]]==dis[0]) { flag=1; break; } sum+=dis[cow[j]]; } if (flag==0) ans=min(ans, sum); } printf("%d", ans); return 0; } /* 2 3 3 1 2 1 2 2 2 3 1 3 1 2 */
标签:le,int,牧场,vis,断网,香甜,黄油,奶牛,dis From: https://www.cnblogs.com/didiao233/p/17991056