台中女中-109-6 超級大轉機

用到了 Bellman-Ford Shortist Path Algorithm

#include<iostream>
using namespace std;
#define INF 1e9

struct edge{
    int from,to,cost;
};

int d[505],c[505],n,m;
edge a[10050];

void shortistPath(){
    while(1){
	bool update=false;
	for(int i=0;i<2*m;i++){
	    if(d[a[i].from]!=INF && 
              d[a[i].to]>d[a[i].from]+a[i].cost+c[a[i].to]){
	        d[a[i].to]=d[a[i].from]+a[i].cost+c[a[i].to];
		update=true;
	    }
	}
	if(!update) break;
    }
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
	cin>>c[i];
	d[i]=INF;
    }

    cin>>m;
    for(int i=0;i<m;i++){
	cin>>a[i].from>>a[i].to>>a[i].cost;
	a[m+i].from=a[i].to;
	a[m+i].to=a[i].from;
	a[m+i].cost=a[i].cost;
    }

    d[1]=0;
    shortistPath();
    if(d[n]!=INF){
	cout<<d[n];//end point
    }else{
	cout<<"-1";
    }

    return 0;
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *