洛谷 P1339 [USACO09OCT]热浪Heat Wave

题目链接:https://www.luogu.org/problemnew/show/P1339

解题思路:

一道简单的最短路水题,dijkstra解法模板思路:https://www.cnblogs.com/lipeiyi520/p/10340361.html

AC代码:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int ff=0x3f3f3f;
 4 int n,m,g[5006][5006],a,b,c; 
 5 bool vis[2501];
 6 int dist[2501];
 7 void dij(int s){
 8     memset(vis,false,sizeof(vis));//初始时所有点都没有确定最短路 
 9     memset(dist,0x3f,sizeof(dist));//答案初始为无限大 
10     dist[s]=0;//原点最短路为0 
11     for(int i=0;i<n;i++){
12         int hh,mind=ff;
13         for(int j=1;j<=n;++j){
14             if(!vis[j]&&dist[j]<mind){//找出于当前点相邻的距当前点最近的点 
15                 mind=dist[j];
16                 hh=j;
17             }
18         }
19         vis[hh]=1;
20         for(int j=1;j<=n;++j){
21             dist[j]=min(dist[j],dist[hh]+g[hh][j]);//如果一个点a到原点距离加点a到当前点的距离小于当前点到原点距离，那么就更新 
22         }
23     }
24 }
25 int main()
26 {
27     int ts,te;
28      memset(g,0x3f,sizeof(g));  //初始化图，是每个点到原点最短路都为无限大 
29     cin>>n>>m>>te>>ts;
30     for(int i=0;i<m;i++){//建图 
31         cin>>a>>b>>c;
32         g[a][b]=c;
33         g[b][a]=c;
34     }
35     dij(ts);
36     cout<<dist[te];
37 return 0;
38 }