题目链接：热浪
题意就是给你一堆路径，然后让你找某两个点之间的最短路，然后一道裸的最短路，写了个SPFA
#include <bits/stdc++.h> using namespace std; const int maxn = 3005; int n,m,s,t; int d[maxn],inq[maxn]; vector<pair<int ,int > >E[maxn]; void init(){ for(int i = 0;i < maxn;i++) E[i].clear(); for(int i = 0;i < maxn;i++) inq[i] = 0; for(int i = 0;i < maxn;i++) d[i] = 1e9; } int main(){ while(cin>>n>>m>>s>>t){ init(); for(int i = 0;i < m;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); E[x].push_back(make_pair(y,z)); E[y].push_back(make_pair(x,z)); } queue<int>Q; Q.push(s),d[s] = 0,inq[s] = 1; while(!Q.empty()){ int now = Q.front(); Q.pop();inq[now] = 0; for(int i = 0;i < E[now].size();i++){ int v = E[now][i].first; if(d[v] > d[now]+E[now][i].second){ d[v] = d[now]+E[now][i].second; if(inq[v] == 1) continue; inq[v] = 1; Q.push(v); } } } if(d[t] == 1e9) cout<<"-1"<<endl; else cout<<d[t]<<endl; } return 0; }