题目描述

blablabla

样例

blablabla

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>

using namespace std;

const int N = 510;

int n,t;
int x,y,z;
int g[N][N];
int dist[N]; // min
bool b[N];
int ans;

int dj()
{
   memset(dist,0x3f,sizeof dist);

   dist[1] = 0;

   for (int i = 0; i < n - 1; i++) 
   {
       int t = -1; // dijksta 不适用于有负权边的图

       for (int j = 1; j <= n; j++) 
           if (!b[j] && (t == -1 || dist[j] < dist[t])) // 寻找未确定的最短路点中路径最短的点
                t = j; 
        b[t] = true; 
        for (int j = 1; j <= n; j++) 
        {
                // 用这个点去更新其他未确定点的最短距离
            dist[j] = min(dist[j], dist[t] + g[t][j]); // O(n) * O(n) -> O(n^2)
        }
    }
if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    cin>>n>>t;
    memset(g,0x3f,sizeof g);
    for(int i = 0; i < t; i++){
        cin>>x>>y>>z;
        g[x][y] = min(g[x][y],z);
        // g[y][x] = g[x][y];
    }
    cout<<dj()<<endl;
    return 0;
}