構造物品的最小花費

2 ． dwarf tower

(dwarf.cpp/c/pas)

【問題描述】

Vasya在玩一個叫做"Dwarf Tower"的遊戲，這個遊戲中有n個不同的物品，

它們的編号為1到n。現在Vasya想得到編号為1的物品。

獲得一個物品有兩種方式：

1. 直接購買該物品，第i件物品花費的錢為ci

2. 用兩件其他物品合成所需的物品，一共有m種合成方式。

請幫助Vasya用最少的錢獲得編号為1的物品。

【輸入格式】

第一行有兩個整數n,m(1<=n<=10000,0<=m<=100000)，分别表示有n種物品以

及m種合成方式。

接下來一行有n個整數，第i個整數ci表示第i個物品的購買價格，其中

0<=ci<=10^9。

接下來m行，每行3個整數ai,xi,yi，表示用物品xi和yi可以合成物品ai，其

中(1<=ai,xi,yi<=n; ai<>xi, xi<>yi, yi<>ai)

【輸出格式】

一行，一個整數表示擷取物品 1 的最少花費。

輸入樣例：  輸出樣例：

5 3

5 0 1 2 5

5 2 3

4 2 3

1 4 5

2

【資料規模與約定】

60%的資料，n<=100

100%的資料，n<=10000，m<=100000

分析：

巧妙地建圖。我們設立0号點，向每個點連d[i]的邊，然後合成則是在xi和ai，yi和ai之間連d[yi],和d[xi]的邊。然後spfa，注意這個合成所連的邊動态的，是以我們記錄邊時，選擇使用對應得标号，而不是直接的值。

參考程式：

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=211000;
queue<int>Q;
bool inq[maxn];
int a[maxn];
struct Edge{
	int j,v,next;
}e[maxn];
int NodeCnt=0,m,n;
int d[maxn];
void addedge(int u,int v,int w){
	int p=++NodeCnt;
	e[p].j=v;e[p].v=w;e[p].next=a[u];
	a[u]=p;
}
void Spfa(){
	for (int i=1;i<=n;i++){
		inq[i]=true;
		Q.push(i);
	}
	while (!Q.empty()){
		int u=Q.front();Q.pop();inq[u]=false;
		for (int p=a[u];p;p=e[p].next){
			int j=e[p].j;
			if (d[j]>d[u]+d[e[p].v]){
				d[j]=d[u]+d[e[p].v];
				if (!inq[j])inq[j]=true,Q.push(j);
			}
		}
	}
}
int main(){
	freopen("dwarf.in","r",stdin);
	freopen("dwarf.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		scanf("%d",&d[i]);
	for (int i=0;i<m;i++){
		int u,v,j;
		scanf("%d%d%d",&u,&v,&j);
		addedge(v,u,j);
		addedge(j,u,v);
	}
	Spfa();
	printf("%d",d[1]);
	return 0;
}