使用简单的数据结构（矩阵）

解题思路:迪杰斯特拉算法

注意事项:

参考代码:

#include<iostream>  
#include <limits>
#include<algorithm>
using namespace std;
#include<string>
#include <vector>
#include <cmath>
int main()
{
    int nn,mm;
    cin>>nn>>mm;
    vector<int>isolate(nn+1);
    vector<vector<int>>roadtime(nn+1,vector<int>(nn+1,0));
    vector<bool>visited(nn+1);
    vector<int>result(nn+1,999999);
    result[1]=0;
    visited[1]=true;
    for(int i=1;i<=nn;i++){
        cin>>isolate[i];
    }
    for(int i=0;i<mm;i++){
        int u,v,c;
        cin>>u>>v>>c;
        roadtime[u][v]=roadtime[v][u]=c;
    }
    /*for(int i=1;i<=nn;i++){
        for(int j=1;j<=nn;j++){
            cout<<roadtime[i][j];
        }
        cout<<endl;
    }*/
    for(int i=1;i<nn;i++){
        for(int j=2;j<nn;j++){
            if(roadtime[i][j]!=0)roadtime[i][j]+=isolate[j];
        }  
    }
    /*for(int i=1;i<=nn;i++){
        for(int j=1;j<=nn;j++){
            cout<<roadtime[i][j];
        }
        cout<<endl;
    }*/
//路径时间加上隔离，最后一个不加
    int current_city=1;
    while(visited[nn]==false){
        int minm=9999999;
        int min_index=nn;
        for(int i=2;i<=nn;i++){
            if(!visited[i]&&result[current_city]+roadtime[current_city][i]<result[i]&&roadtime[current_city][i]!=0){
                result[i]=result[current_city]+roadtime[current_city][i];
            }//更新
        }    //不为零就是可抵达，找最小的
        for(int i=2;i<=nn;i++){
            if(result[i]<minm&&!visited[i]){
                minm=result[i];
                min_index=i;

            }
        }
        current_city=min_index;
        visited[min_index]=true;
        //更新
    }
    cout<<result[nn];
}