不写普通模板了,还是需要优先队列优化的昂
#include<stdio.h> //基本需要的头文件
#include<string.h>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f; const int maxn=1e5+;
const int maxm=1e5+; int head[maxn],nxt[maxm<<],val[maxm<<],point[maxm<<],size;
int dis[maxn]; void init(){
memset(head,-,sizeof(head));
size=;
} void add(int a,int b,int v){ //若有向图则只需要前一半
point[size]=b;
val[size]=v;
nxt[size]=head[a];
head[a]=size++; point[size]=a;
val[size]=v;
nxt[size]=head[b];
head[b]=size++;
} struct cmp{ //将优先队列改为小根堆
bool operator()(pii a,pii b){
return a.first>b.first;
}
}; void dij(int s,int t){ //传入出发点和到达点
int i;
priority_queue<pii,vector<pii>,cmp>q;
q.push(make_pair(,s));
memset(dis,0x3f,sizeof(dis));
dis[s]=;
while(!q.empty()){
pii u=q.top();
q.pop();
if(u.first>dis[u.second])continue;
for(i=head[u.second];~i;i=nxt[i]){
int j=point[i];
if(dis[j]>u.first+val[i]){
dis[j]=u.first+val[i];
q.push(make_pair(dis[j],j));
}
}
}
printf("%d\n",dis[t]); //或去掉在主函数中输出或操作
}
最开始是因为寒假集训的时候学长讲的用pair存进优先队列的,实际上我更喜欢用结构体重载运算符来实现,所以也放上来。
另外……之前上面的代码里……有个size打成了sise,但是因为平时直接手敲,所以没有用这个贴过题,一直没有发现,甚至还看到有某些不明真相的网站把这篇复制粘贴过去了,非常的尴尬233333
反正我不尴尬啦
#include<stdio.h> //基本需要的头文件
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f; const int maxn=1e3+;
const int maxm=1e5+; struct pii{
int dis;
int s;
bool operator < (const pii x)const{
return dis > x.dis;
}
pii(int a,int b):dis(a),s(b){};
};
int head[maxn],nxt[maxm<<],val[maxm<<],point[maxm<<],size;
int dis[maxn]; void init(){
memset(head,-,sizeof(head));
size=;
} void add(int a,int b,int v){
point[size]=b;
val[size]=v;
nxt[size]=head[a];
head[a]=size++;
} void dij(int s,int t){ //传入出发点和到达点
int i;
priority_queue<pii>q;
q.push(pii(,s));
memset(dis,0x3f,sizeof(dis));
dis[s]=;
while(!q.empty()){
pii u=q.top();
q.pop();
if(u.dis>dis[u.s])continue;
for(i=head[u.s];~i;i=nxt[i]){
int j=point[i];
if(dis[j]>u.dis+val[i]){
dis[j]=u.dis+val[i];
q.push(pii(dis[j],j));
}
}
}
printf("%d\n",dis[t]); //或去掉在主函数中输出或操作
}