题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=510;
int g[N][N];//当前位置上是稠密图   因为当前位置上 线的个数大于点的个数
int dict[N];
bool st[N];
int n,m;
int Dj(){
    memset(dict,0x3f,sizeof dict);
    dict[1]=0;
    for(int i=1;i<=n;i++){
        int res=-1;
        for(int j=1;j<=n;j++){
            if(!st[j]&&(res==-1||dict[res]>dict[j])){
                res=j;
            }
        }
        st[res]=true;//表示当前这个数字被选择，接下来根据该数字来更新与该数字有关的数字
        for(int j=1;j<=n;j++){
            dict[j]=min(dict[j],dict[res]+g[res][j]);
        }        

    }
    if(dict[n]==0x3f3f3f3f){
        return -1;
    }else{
        return dict[n];
    }
}
int main(){
    scanf("%d %d",&n,&m);//因为要求的是最短路，所以刚开始把每个点都设置为无穷大
    memset(g,0x3f,sizeof g);
    for(int i=1;i<=m;i++){
        int a,b,w;
        scanf("%d %d %d",&a,&b,&w);
        g[a][b]=min(g[a][b],w);
    }
    int tt=Dj();
    cout<<tt;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla