Chri_K

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=510;

int g[N][N];    //為稠密陣所以用鄰接矩陣存儲
int dist[N];    //用于記錄每一個點距離第一個點的距離
bool st[N];     //用于記錄該點的最短距離是否已經(jīng)確定

int n,m;

int Dijkstra()
{
    memset(dist, 0x3f,sizeof dist);     //初始化距離  0x3f代表無限大

    dist[1]=0;  //第一個點到自身的距離為0

    for(int i=0;i<n;i++)      //有n個點所以要進(jìn)行n次 迭代
    {
        int t=-1;       //t存儲當(dāng)前訪問的點

        for(int j=1;j<=n;j++)   //這里的j代表的是從1號點開始
            if(!st[j]&&(t==-1||dist[t]>dist[j]))     
                t=j;

        st[t]=true;   

        for(int j=1;j<=n;j++)           //依次更新每個點所到相鄰的點路徑值
            dist[j]=min(dist[j],dist[t]+g[t][j]);
    }

    if(dist[n]==0x3f3f3f3f) return -1;  //如果第n個點路徑為無窮大即不存在最低路徑
    return dist[n];
}
int main()
{
    cin>>n>>m;

    memset(g,0x3f,sizeof g);    //初始化圖 因為是求最短路徑
                                //所以每個點初始為無限大

    while(m--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        g[x][y]=min(g[x][y],z);     //如果發(fā)生重邊的情況則保留最短的一條邊
    }

    cout<<Dijkstra()<<endl;
    return 0;
}