洛谷P 1828【甘いバターSweet Butter】
1259 ワード
この問題はテンプレートの問題でしょうqwq.
各牧場の砂糖を入れる状況を統計して、最適なものを選ぶと億点の水の緑の問題があります.
各牧場の砂糖を入れる状況を統計して、最適なものを選ぶと億点の水の緑の問題があります.
#include
using namespace std;
int n , p , c , ans = 0x3ffffff , sum;
int vis[810] , dis[810] , f[810];
vector > e[810]; //vector ~
void work(int s){ //
// , SPFA , SPFA qnq
priority_queue > q;
memset(dis , 127 , sizeof(dis));
memset(f , 0 , sizeof(f));
dis[s] = 0;
q.push(make_pair(0 , s));
while(!q.empty()){
int x = q.top().second;
q.pop();
if(f[x]) continue;
f[x] = 1;
for(int i = 0; i < e[x].size(); i++){
int nx = e[x][i].first , w = e[x][i].second;
if(dis[nx] > dis[x] + w){
dis[nx] = dis[x] + w;
q.push(make_pair(-dis[nx] , nx));
}
}
}
}
int main(){
cin >> n >> p >> c;
for(int i = 1; i <= n; i++){
int x;
cin >> x;
vis[x]++; //
}
for(int i = 1; i <= c; i++){
int x , y , z;
cin >> x >> y >> z;
e[x].push_back(make_pair(y , z));
e[y].push_back(make_pair(x , z));
}
for(int i = 1; i <= p; i++){
sum = 0;
work(i);
for(int j = 1; j <= p; j++) sum += (vis[j] * dis[j]); //
ans = min(ans , sum);
}
cout << ans;
return 0;
}