题解 | #小木乃伊到我家#

一手BellmanFord算法送给大家（感觉应该是最容易写的）

我把自己给坑到了！注意此题是无向图，所以两个方向的边都需要存下！

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

struct node{
    ll u,v,w;
};

int main ()
{
    int n,m;
    cin>>n>>m;
    ll u,v,w;
    vector<node>graph(m*2);    //注意题目是无向图！！！需要存储两个方向的边！
    for(int i=0;i<m;i++){
        cin>>u>>v>>w;
        graph[i] = {u,v,w};
        graph[m+i] = {v,u,w};
    }
    vector<ll>dp(n+5,LLONG_MAX/2);
    dp[1] = 0;
    for(int i=0;i<n-1;i++){
        bool  f = true;
        for(int j=0;j<2*m;j++){
            if(dp[graph[j].v]>dp[graph[j].u]+graph[j].w){
                dp[graph[j].v] = dp[graph[j].u]+graph[j].w;
                f = false;
            }
        }
        if(f)
            break;
    }
    if(dp[n]==LLONG_MAX/2){
        cout<<"qwb baka\n";
    }else{
        cout<<dp[n];
    }
    return 0;
}