看似不是單源點最短路的，單源點最短路。其實這個題目說讓你求出這些邊的價值，剛開始誤以為是最小生成樹，挺像的，但是邊的權值你不好算。因為每條邊的權值= (sum of weights of all descendant nodes) × (unit price of the edge)，然後腦子裡面yy出一張圖，其實你算每個節點的價值，算出然後求和就是這個題目要求的。然後單源點最短路徑就出現了，直接套用spfa模板，然後就水過了。呵呵。
[cpp]
<SPAN style="FONT-SIZE: 18px">#include<iostream>
#include<queue>
#include<cstring>
#include<stdio.h>
using namespace std;
struct edge{
long long start;
long long end;
long long len;
long long next;
};
long long tot;
long long list[50010];
edge D[100010];
long long dist[50010];
bool vis[50010];
long long weight[50010];
void add(long long a,long long b,long long c)
{
tot=tot+1;
D[tot].start=a;
D[tot].end=b;
D[tot].len=c;
D[tot].next=list[a];
list[a]=tot;
}
void spfa()
{
long long i;
queue<long long> qu;
long long now=1;
memset(vis,false,sizeof(vis));
memset(dist,-1,sizeof(dist));
vis[now]=true;
dist[now]=0;
qu.push(now);
while(!qu.empty())
{
now=qu.front();
qu.pop();
vis[now]=false;
for(i=list[now];i!=-1;i=D[i].next)
{
long long temp;
temp=dist[now]+D[i].len;
if(temp<dist[D[i].end]||dist[D[i].end]==-1)
{
dist[D[i].end]=temp;
if(vis[D[i].end]==false)
{
vis[D[i].end]=true;
qu.push(D[i].end);
}
}
}
}
}
int main()
{
long long T,sum,i,m,n,a,b,c,flag;
cin>>T;
while(T--)
{
memset(list,-1,sizeof(list));
sum=0;
flag=0;
tot=0;
cin>>n>>m;
for(i=1;i<=n;i++)
scanf("%lld",&weight[i]);
for(i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
spfa();
for(i=2;i<=n;i++)
{
if(dist[i]==-1)
{
flag=1;
break;
}
sum=sum+weight[i]*dist[i];
}
if(flag==1)
cout<<"No Answer"<<endl;
else cout<<sum<<endl;
}
return 0;
}
</SPAN>
#include<iostream>
#include<queue>
#include<cstring>
#include<stdio.h>
using namespace std;
struct edge{
long long start;
long long end;
long long len;
long long next;
};
long long tot;
long long list[50010];
edge D[100010];
long long dist[50010];
bool vis[50010];
long long weight[50010];
void add(long long a,long long b,long long c)
{
tot=tot+1;
D[tot].start=a;
D[tot].end=b;
D[tot].len=c;
D[tot].next=list[a];
list[a]=tot;
}
void spfa()
{
long long i;
queue<long long> qu;
long long now=1;
memset(vis,false,sizeof(vis));
memset(dist,-1,sizeof(dist));
vis[now]=true;
dist[now]=0;
qu.push(now);
while(!qu.empty())
{
now=qu.front();
qu.pop();
vis[now]=false;
for(i=list[now];i!=-1;i=D[i].next)
{
long long temp;
temp=dist[now]+D[i].len;
if(temp<dist[D[i].end]||dist[D[i].end]==-1)
{
dist[D[i].end]=temp;
if(vis[D[i].end]==false)
{
vis[D[i].end]=true;
qu.push(D[i].end);
}
}
}
}
}
int main()
{
long long T,sum,i,m,n,a,b,c,flag;
cin>>T;
while(T--)
{
memset(list,-1,sizeof(list));
sum=0;
flag=0;
tot=0;
cin>>n>>m;
for(i=1;i<=n;i++)
scanf("%lld",&weight[i]);
for(i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
spfa();
for(i=2;i<=n;i++)
{
if(dist[i]==-1)
{
flag=1;
break;
}
sum=sum+weight[i]*dist[i];
}
if(flag==1)
cout<<"No Answer"<<endl;
else cout<<sum<<endl;
}
return 0;
}
