题目描述

给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。

输入格式
第一行包含整数n和m。

接下来m行每行包含三个整数x，y，z，表示点x和点y之间存在一条有向边，边长为z。

输出格式
输出一个整数，表示1号点到n号点的最短距离。

如果路径不存在，则输出-1。

数据范围
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。

样例

输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3

算法1

(dijkstra)

题解:
由于n,m相差太多，是一个稠密图，所以用邻接矩阵来存储与操作！
时间复杂度分析：程序时间复杂度为O(n^2),主要问题是在搜索全局最小值得过程中，可以用二叉堆对dist数组经行维护，用O（log(n)）得时间获取最小值并从堆中删除，用O（logn）得时间执行一条边得扩展和更新，最终时间复杂度可在O(mlogn)的时间实现dijkstra算法！但是考虑到用于便于点所以时间复杂度为O（m+nlogn）！

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
const  int N=510;
int g[N][N],dist[N],n,m;
bool st[N];


int dijkstrac(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++)
        if(!st[j]&&(t==-1||dist[j]<dist[t]))
                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;
    return dist[n];
}
int main(){
   cin.tie(0);
   ios::sync_with_stdio(false);
   cin>>n>>m;
   memset(g,0x3f,sizeof g);
   while(m--)
   {
       int a,b,c;
       cin>>a>>b>>c;
       g[a][b]=min(g[a][b],c);
   }
   cout<<dijkstrac()<<endl;
   return 0;
}