POJ 3013 Big Christmas Tree最短
テーマは次のとおりです.
いくつかの点があり、各点には重量値があり、次にいくつかのエッジが与えられ、各エッジには重み値があります.
最後に、いくつかのエッジで木を構成し、各エッジ(u,v)のコストを最小限に抑える=(すべての子孫ノードの重量と)*(エッジの重み値)
この費用については,各エッジ(u,v)について,その費用は後のノードごとにこのエッジを1回歩いたことに相当することが分かる.
では、最良の木が形成されていると仮定して、この木を観察すると、1つの辺(u,v)について、辺の子供がこの辺を1回歩いたため、1本の木の中で、根の結点から辺のある子供の結点までの経路は必然的に(u,v)、他の辺は同じで、すべての辺の費用の和を含んでいることがわかります.ルートノードからあるノードへのパス長*ノード重量の和に変換すると最短パスを求めることになります
では、すべての点の最短経路は必ず木ですか?これは明らかです.リングが形成されると、ある点に着くと複数のパスが現れ、長いものを削除してリングがないようにします.
そしてこの問題で注意しなければならないのは、intを超えるところがあるので、int 64にすればいいので、INFの値も大きく設定します.例えば100億、最短経路の限界データは5 W*2^16>2^31だから
いくつかの点があり、各点には重量値があり、次にいくつかのエッジが与えられ、各エッジには重み値があります.
最後に、いくつかのエッジで木を構成し、各エッジ(u,v)のコストを最小限に抑える=(すべての子孫ノードの重量と)*(エッジの重み値)
この費用については,各エッジ(u,v)について,その費用は後のノードごとにこのエッジを1回歩いたことに相当することが分かる.
では、最良の木が形成されていると仮定して、この木を観察すると、1つの辺(u,v)について、辺の子供がこの辺を1回歩いたため、1本の木の中で、根の結点から辺のある子供の結点までの経路は必然的に(u,v)、他の辺は同じで、すべての辺の費用の和を含んでいることがわかります.ルートノードからあるノードへのパス長*ノード重量の和に変換すると最短パスを求めることになります
では、すべての点の最短経路は必ず木ですか?これは明らかです.リングが形成されると、ある点に着くと複数のパスが現れ、長いものを削除してリングがないようにします.
そしてこの問題で注意しなければならないのは、intを超えるところがあるので、int 64にすればいいので、INFの値も大きく設定します.例えば100億、最短経路の限界データは5 W*2^16>2^31だから
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define LOCA
#define MAXN 50005
#define INF 10000000000LL
#define eps 1e-7
using namespace std;
struct node
{
int v;
__int64 w;
node *next;
} edge[MAXN], temp[2 * MAXN];
int n, m, pos;
__int64 d[MAXN];
int q[MAXN * 4];
bool visited[MAXN];
__int64 weight[MAXN];
void spfa(int src, __int64 *ecost) //src , ecost
{
int h, t, u;
node *ptr;
h = 0, t = 1;
memset(visited, 0, sizeof(visited));
q[0] = src;
ecost[src] = 0;
visited[src] = true;
while(h < t)
{
u = q[h++];
visited[u] = false;
ptr = edge[u].next;
while(ptr)
{
if(ecost[ptr -> v] > ecost[u] + ptr -> w)
{
ecost[ptr -> v] = ecost[u] + ptr -> w;
if(!visited[ptr -> v])
{
q[t++] = ptr -> v;
visited[ptr -> v] = true;
}
}
ptr = ptr -> next;
}
}
}
void insert(const int &x, const int &y, const __int64 &w)
{
node *ptr = &temp[pos++];
ptr -> v = y;
ptr -> w = w;
ptr -> next = edge[x].next;
edge[x].next = ptr;
}
void init()
{
pos = 0;
for(int i = 0; i <= n; i++)
{
edge[i].next = NULL;
d[i] = INF;
}
}
int main()
{
int T, u, v;
__int64 w;
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &n, &m);
init();
for(int i = 1; i <= n; i++)
scanf("%I64d", &weight[i]);
for(int i = 0; i < m; i++)
{
scanf("%d%d%I64d", &u, &v, &w);
insert(u, v, w);
insert(v, u, w);
}
spfa(1, d);
int flag = 0;
__int64 ans = 0;
for(int i = 1; i <= n; i++)
{
if(d[i] == INF)
{
flag = 1;
break;
}
ans += weight[i] * d[i];
}
if(flag) printf("No Answer
");
else printf("%I64d
", ans);
}
return 0;
}