打卡信奥刷题（986）用C++实现信奥 P1339 [USACO09OCT] Heat Wave G

rogeliu

5964人浏览 · 2025-03-20 07:15:37

rogeliu · 2025-03-20 07:15:37 发布

P1339 [USACO09OCT] Heat Wave G

题目描述

有一个 $n$ 个点 $m$ 条边的无向图，请求出从 $s$ 到 $t$ 的最短路长度。

输入格式

第一行四个正整数 $n, m, s, t$ 。
接下来 $m$ 行，每行三个正整数 $u, v, w$ ，表示一条连接 $u, v$ ，长为 $w$ 的边。

输出格式

输出一行一个整数，表示答案。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

【数据范围】
对于 $100%100\%$ 的数据， $1≤n≤25001\le n \le 2500$ ， $1≤m≤62001\le m \le 6200$ ， $1≤w≤10001\le w \le 1000$ 。

【样例说明】
$\to 6 \to 1 \to 4$ 为最短路，长度为 $3 + 1 + 3 = 7$ 。

C++实现

#include<bits/stdc++.h>
using namespace std;
const int maxn=2505;
#define INF 1e9
vector<pair<int,int> >e[maxn];
int d[maxn];
void dijkstra(int s){
priority_queue<pair<int,int> >q;//大根堆
d[s]=0;
q.push(make_pair(-d[s],s));
while(!q.empty()){
int now=q.top().second;
q.pop();
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;
q.push(make_pair(-d[v],v));
}
}
}
}
int main() {
int n,m,s,t;
scanf(“%d%d%d%d”,&n,&m,&s,&t);
for(int i=0;i<maxn;i++)e[i].clear(),d[i]=INF;
for(int i=1;i<=m;i++) {//建图
int u,v,d;
scanf(“%d%d%d”,&u,&v,&d);
e[u].push_back(make_pair(v,d));
e[v].push_back(make_pair(u,d));
}
dijkstra(s);
printf(“%d\n”,d[t]);
return 0;
}