最短路的蒻弱化版，借着练了一遍dij堆优化的板子，放一个dij的标程在这吧。（真心感觉dij比某个已死算法敲着简单）

堆优化部分：

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 
struct node { int u,v; bool operator <(const node &b)const { return u>b.u; } }; priority_queue<node>q;

核心程序

void dijkstra() { for(int i=0;i<=n;i++) dis[i]=inf; dis[s]=0; node k; k.u=0; k.v=s; q.push(k); while(!q.empty()) { int k=q.top().v,d=q.top().u; q.pop(); if(dis[k]!=d) continue; for(int i=head[k];i;i=ed[i].nxt) { if(dis[ed[i].to]>dis[k]+ed[i].val) { dis[ed[i].to]=dis[k]+ed[i].val; node p; p.v=ed[i].to; p.u=dis[p.v]; q.push(p); } } } }

完整代码（规定起止点的dij）

#include<cstdio> #include<algorithm> #include<cstring> #include<queue>
#define maxn 100010
#define inf 2120030207
using namespace std; int head[maxn],dis[maxn],n,m,s,t,vis[maxn]; struct noded { int nxt,to,val; }ed[maxn<<1]; int cnt; void add(int x,int y,int z) { ed[++cnt].to=y; ed[cnt].nxt=head[x]; head[x]=cnt; ed[cnt].val=z; swap(x,y); ed[++cnt].to=y; ed[cnt].nxt=head[x]; head[x]=cnt; ed[cnt].val=z; } struct node { int u,v; bool operator <(const node &b)const { return u>b.u; } }; priority_queue<node>q; void dijkstra() { for(int i=0;i<=n;i++) dis[i]=inf; dis[s]=0; node k; k.u=0; k.v=s; q.push(k); while(!q.empty()) { int k=q.top().v,d=q.top().u; q.pop(); if(dis[k]!=d) continue; for(int i=head[k];i;i=ed[i].nxt) { if(dis[ed[i].to]>dis[k]+ed[i].val) { dis[ed[i].to]=dis[k]+ed[i].val; node p; p.v=ed[i].to; p.u=dis[p.v]; q.push(p); } } } } int main() { scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1,a,b,c;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); add(a,b,c); } dijkstra(); printf("%d\n",dis[t]); return 0; }

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄