lanqiao OJ 2194 出差 bellman—ford

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std ;
const int INF = 0x3f3f3f3f ;
const int N = 20010 ;
struct edge{
  int a , b , c ;
}e[N];
int t[N] ;
int dis[N] ;
int n , m ;
int main(){
  cin >> n >> m ;
  for(int i = 1 ; i <= n ;i ++) cin >> t[i] ;
  for(int i = 1 ; i <= m ; i ++){
    int a, b ,c ;
    cin >> a >> b >> c ;
    e[i].a = a , e[i].b = b , e[i].c = c ;
    e[i+m].a = b , e[i+m].b = a , e[i+m].c = c ; 
  }
  memset(dis,INF ,sizeof(dis)) ;
  dis[1] = 0 ;
  for(int k = 1 ; k <= n ; k ++){
    for(int i = 1 ; i <= 2*m ; i ++){
      int u = e[i].a , v = e[i].b ;
      int res = t[v] ;
      if(v == n) res = 0 ;
      dis[v] = min(dis[v],dis[u] + res + e[i].c) ;
    }
  }
  cout << dis[n] << endl ;
}