这是一道Dijkstra经典题目(裸题)
P2299Mzc和体委的争夺战
代码思路:Dijkstra+链式前向星+优先队列+结构体
其实很简单的
重点:
if(vis[n])
return ;
意思是找到了立即返回,这样可以节约许些时间
代码核心:
inline void dijkstra(int u){
priority_queue<node>q;
memset(dist, INF,sizeof(dist));
dist[u] = 0;
q.push(node(u,dist[u]));
while(!q.empty()){
int v = q.top().u;
q.pop();
if(vis[n])
return ;
if(vis[v])
continue;
vis[v] = 1;
//这里我写复杂了
for(int i = head[v];i;i = E[i].next){
if(!vis[E[i].to]&&dist[E[i].to]>dist[v]+E[i].w){
dist[E[i].to] = dist[v] + E[i].w;
q.push(node(E[i].to,dist[E[i].to]));
}
}
}
}
将Dijkstra稍微改一改,符合题意即可
这是实现优先队列内部从小到大以dist为标准排序
运用了重载运算符
bool operator < (const node &a)const {
return dist > a.dist;
}
下面是完整代码
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 2505;
const int INF = 0x3f3f3f3f;
inline int read(){
int x = 0;char c = getchar();
while(c<'0'||c > '9') c = getchar();
while(c>='0'&& c <='9') x = (x<<1)+(x<<3)+(c^48),c = getchar();
return x;
}
struct node{
int u, dist;
node(){};
node(int u_,int dist_){
u = u_,dist = dist_;
}
bool operator < (const node &a)const {
return dist > a.dist;
}
};
struct edge{
int to,next,w;
}E[maxn*maxn];
int head[maxn];
int cnt;
inline void add(int u,int v,int w){
E[++cnt].to = v;
E[cnt].w = w;
E[cnt].next = head[u];
head[u] = cnt;
}
int n,m;
int dist[maxn];
bool vis[maxn];
inline void dijkstra(int u){
priority_queue<node>q;
memset(dist, INF,sizeof(dist));
dist[u] = 0;
q.push(node(u,dist[u]));
while(!q.empty()){
int v = q.top().u;
q.pop();
if(vis[n])
return ;
if(vis[v])
continue;
vis[v] = 1;
//这里我写复杂了
for(int i = head[v];i;i = E[i].next){
if(!vis[E[i].to]&&dist[E[i].to]>dist[v]+E[i].w){
dist[E[i].to] = dist[v] + E[i].w;
q.push(node(E[i].to,dist[E[i].to]));
}
}
}
}
int main(){
n = read(),m = read();
int u,v,w;
memset(head,-1,sizeof(head));
for(int i = 0;i<m;i++){
u = read(), v = read(), w = read();
add(u,v,w);
add(v,u,w);
}
dijkstra(1);
cout << dist[n];
return 0;
}
下面是提交结果:
膜拜youyi2008大佬 他老人家是第一
标签:head,dist,int,题解,cnt,P2299Mzc,体委,vis,maxn From: https://www.cnblogs.com/adidecd/p/16840485.html