出差，dij算法

解题思路:使用图dijistra算法，根据题目进行一点变形即可

注意事项:
注意算法时间复杂度，以及一些小细节，代码中都有详细注释
参考代码:

#include<bits/stdc++.h>

#define MAX 20000

using namespace std;

int N,M;

//bool con(vector<vector<int>> lu,int s,int e)  //判断两个城市是否连接 ，其实是没有必要的 

//{

// if(lu[s][e]<MAX||lu[e][s]) return true;

// return false;

//}

int findmin(vector<int> lenv,vector<int> yes)  //找当前未确定城市中耗时最小的 

{   int minj=MAX,min=MAX; //注意初值应该为最大 

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

{

if(lenv[i]<min&&!yes[i])

{min=lenv[i];minj=i;}

}

return minj;

}

int main() 

{   

    ios::sync_with_stdio(false);

cin.tie(0);

cout.tie(0);

    cin>>N>>M;

    vector<int> geli(N+1);   //隔离时间 

    vector<vector<int>> lu(N+1,vector<int> (N+1,MAX));   //路程

vector<int> yes(N+1,0),lenv(N+1,MAX); //确定数组和到达城市耗时数组 

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

    {

    cin>>geli[i];

}

geli[1]=0;geli[N]=0;  //根据题目要求，可以直接让起始和结尾城市的隔离时间为0 

lenv[1]=0;

int s,e,len;

for(int i=0;i<M;i++)

{

cin>>s>>e>>len;

lu[s][e]=len+geli[e];  //新的路径长度为本来的路程加上疫情隔离时间 

lu[e][s]=len+geli[s];  //注意lu[e][s]的值并不等于lu[s][e],因为终点城市不一样，隔离时间有变化 

}

while(!yes[N])  //终点还没找到最佳，就继续

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

{

int k=findmin(lenv,yes);

yes[k]=1;

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

{

if(!yes[i])

{

lenv[i]=min(lenv[k]+lu[k][i],lenv[i]);  //不需要判断是否连通，如果不连通的话路径必然会更长 

}

}

}

cout<<lenv[N]<<'\n';

    return 0;

}