例题1.单源最短路径
dij 板子。（w36557658 原版 dij 代码!
code
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int N=100005;
const int M=500005;
const int INF=2147483647;
inline int read(){
int X=0,w=0;char ch=0;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
}
struct node{
int w,to,nxt;
}e[M];
int n,m,k,p,cnt,head[N],dis[N];
bool vis[N];
inline void add(int u,int v,int w){
e[++cnt].to=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt;
}
priority_queue<pii,vector<pii>,greater<pii> >q;
void dij(int s){
dis[s]=0;q.push(pii(0,s));
while(!q.empty()){
int u=q.top().se,f=q.top().fi;q.pop();
if(f!=dis[u])continue;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to,w=e[i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push(pii(dis[v],v));
}
}
}
return;
}
int main(){
int n=read(),m=read(),s=read();
for(int i=1;i<=n;i++)dis[i]=INF;
for(int i=1;i<=m;i++){
int u=read(),v=read(),w=read();
add(u,v,w);
}
dij(s);
for(int i=1;i<=n;i++)printf("%d ",dis[i]);
return 0;
}
例题2.负环判断
板子。坑人，交了一面才发现 std 没清空队列导致数据锅了。
写的时候记得不要清空队列（bushi
code
#include<bits/stdc++.h>
using namespace std;
const int N=6e4+5;
int T,n,m;
int head[N],cnt;
struct node{
int nxt,to,w;
}e[N];
void add(int u,int v,int w){
e[++cnt]={head[u],v,w};head[u]=cnt;
}
int dis[N],in[N],vis[N];
queue<int> q;
bool spfa(int s)
{
memset(dis,0x3f3f3f3f,sizeof(dis));
memset(in,0,sizeof(in));
memset(vis,0,sizeof(vis));
q.push(s);in[s]=1;dis[s]=0;
while(!q.empty())
{
int u=q.front();q.pop();in[u]=0;
//cout<<u<<endl;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(dis[u]+e[i].w<dis[v])
{
dis[v]=dis[u]+e[i].w;
vis[v]=vis[u]+1;
if(vis[v]>=n) return 0;
if(!in[v])
{
in[v]=1;
q.push(v);
}
}
}
}
return 1;
}
int main()
{
scanf("%d",&T);
while(T--)
{
memset(e,0,sizeof(e));
memset(head,0,sizeof(head));cnt=0;
scanf("%d%d",&n,&m);
for(int i=1,u,v,w;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
if(w>=0) add(u,v,w),add(v,u,w);
else add(u,v,w);
}
if(!spfa(1)) cout<<"YE5"<<endl;
else cout<<"N0"<<endl;
}
return 0;
}