Luogu P1339 热浪Heat Wave
裸·单源最短路。
但是!
有以下坑点:
- 算过复杂度发现Floyd跑不过去就不要用了。
- 如果建边是双向边,边的数组大小要开两倍!
- 考场上如果再把初始化的\(dis[i]=INF\)写成\(dis[n]=INF\),或者忘记\(dis[s]=0\)之类的话,就直接火葬场了……
#include<bits/stdc++.h>
#define N 2510
#define M 6210
#define INF 0x3f3f3f3f
using namespace std;
int n,m,s,e,cnt;
int head[M*2],dis[N];
struct node {
int nxt,to,val;
bool operator < (const node& rhs) const {
return rhs.val<val;
}
}edge[M*2];
struct headnode {
int u,d;
bool operator < (const headnode& rhs) const {
return rhs.d<d;
}
};
void addEdge(int u,int v,int w) {
edge[++cnt]=(node){head[u],v,w};
head[u]=cnt;
return;
}
void Read() {
scanf("%d%d%d%d",&n,&m,&s,&e);
for(int i=1;i<=m;i++) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addEdge(u,v,w);
addEdge(v,u,w);
}
return;
}
void Init() {
for(int i=1;i<=n;i++) {
dis[i]=INF;
}
dis[s]=0;
return;
}
void Dijkstra() {
priority_queue <headnode> q;
q.push((headnode){s,dis[s]});
while(!q.empty()) {
headnode x=q.top();
q.pop();
int u=x.u;
if(x.d<dis[u]) {
continue;
}
for(int i=head[u];i;i=edge[i].nxt) {
int v=edge[i].to,w=edge[i].val;
if(dis[u]+w<dis[v]) {
dis[v]=dis[u]+w;
q.push((headnode){v,dis[v]});
}
}
}
return;
}
void Print() {
printf("%d",dis[e]);
return;
}
int main()
{
Read();
Init();
Dijkstra();
Print();
return 0;
}