DFS解法，很简单，通用！

解题思路:暴力的dfs，列举出每条路线的时间，取最小值，因为dfs容易超时，所以当时间超过最小值，这条路线就放弃；还要注意双向边的赋值问题

注意事项:

参考代码:

#include<stdio.h>

#define MAX 1001

int N,M;

int waitTime[MAX];

int arr[MAX][MAX];

int visit[MAX];

int min=10000;

int time=0;

void DFS(int u){

if(time>min){

return;

}

if(u==N){

if(time<min){

min=time;

}

return;

}

for(int j=1;j<=N;j++){

if(visit[j]==0&&arr[u][j]!=0){

time+=arr[u][j];

if(j!=N){

time+=waitTime[j];

}

visit[j]=1;

DFS(j);

time-=arr[u][j];

if(j!=N){

time-=waitTime[j];

}

visit[j]=0;

}

}

}

int main(){

visit[1]=1;

scanf("%d %d",&N,&M);

for(int i=1;i<=N;i++){

scanf("%d",&waitTime[i]);

}

for(int i=1;i<=M;i++){

int u,v,c;

scanf("%d %d %d",&u,&v,&c);

arr[u][v]=c;

arr[v][u]=c;//矩阵赋值要注意是双向边还是单向边； 

}

DFS(1);

printf("%d",min);

return 0;

}