Description
給出一幅由n個(gè)點(diǎn)m條邊構(gòu)成的無(wú)向帶權(quán)圖。
其中有些點(diǎn)是黑點(diǎn)，其他點(diǎn)是白點(diǎn)。
現(xiàn)在每個(gè)白點(diǎn)都要與他距離最近的黑點(diǎn)通過(guò)最短路連接（如果有很多個(gè)黑點(diǎn)，可以選取其中任意一個(gè)），我們想要使得花費(fèi)的代價(jià)最小。請(qǐng)問(wèn)這個(gè)最小代價(jià)是多少？
注意：最后選出的邊保證每個(gè)白點(diǎn)到離它最近的黑點(diǎn)的距離仍然等于原圖中的最短距離。

Input
第一行兩個(gè)整數(shù)n，m；
第二行n 個(gè)整數(shù)，0表示白點(diǎn)，1 表示黑點(diǎn)；
接下來(lái)m 行，每行三個(gè)整數(shù)x，y，z，表示一條連接x和y 點(diǎn)，權(quán)值為z 的邊。

Output
如果無(wú)解，輸出impossible；
否則，輸出最小代價(jià)。

Sample Input
5 7
0 1 0 1 0
1 2 11
1 3 1
1 5 17
2 3 1
3 5 18
4 5 3
2 4 5

Sample Output
5
【樣例解釋】
選 2、4、6三條邊

Data Constraint
對(duì)30%的輸入數(shù)據(jù)： 1≤n≤10， 1≤m≤20；
對(duì)100%的輸入數(shù)據(jù)：1≤n≤100000，1≤m≤200000，1≤z≤1000000000
.
.
.
.
.

分析

.
.
.
.
.

程序：

#include<iostream> #include<string.h> #include<algorithm> #include<queue> using namespace std; struct edge {long long to,from,v; }e[600001],k[600001]; queue<int>q; int inf=0x3f3f3f; long long d[100001],ans,fa[100001],n,m,head[100001],c,t; bool f[100001];void spfa() {memset(d,inf,sizeof(d));memset(f,false,sizeof(f));q.push(0); d[0]=0;while (!q.empty()){int u=q.front(); q.pop();f[u]=false;for (int i=head[u];i;i=e[i].from)if (d[u]+e[i].v<d[e[i].to]){d[e[i].to]=d[u]+e[i].v;if (!f[e[i].to]){q.push(e[i].to);f[e[i].to]=true;}}} }void dg(int x) {for (long long i=head[x];i;i=e[i].from)if (d[x]+e[i].v==d[e[i].to]){dg(e[i].to);k[++t].from=x;k[t].to=e[i].to;k[t].v=e[i].v;} }long long getfather(int x) {if (fa[x]==x) return x;return fa[x]=getfather(fa[x]); }void work() {for (int i=1;i<=n;i++) fa[i]=i;for (long long i=1;i<=t;i++){long long x=getfather(k[i].from),y=getfather(k[i].to);if (x!=y){ans+=k[i].v;fa[y]=x;}} }bool cmp(edge x,edge y) { return x.from<y.from; }void add(int x,int y,int z) { e[++c].to=y; e[c].from=head[x]; e[c].v=z; head[x]=c; }int main() {cin>>n>>m;for (int i=1;i<=n;i++){int x;cin>>x;if (x==1) add(0,i,0);}for (int i=1;i<=m;i++){int x,y,z;cin>>x>>y>>z;add(x,y,z); add(y,x,z);}spfa();dg(0);sort(k+1,k+t+1,cmp);work();if (ans==0) cout<<"impossible"; else cout<<ans; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9499928.html

總結(jié)

以上是生活随笔為你收集整理的【NOIP2015模拟10.22】最小代价的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。