台中女中 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];
    }else{
        cout<<"-1";
    }
    return 0;
}