2023年7月30日发(作者：)

最短路的⼏个板⼦题Dijkstra：题⽬链接：求解1~n的最短路 （双向边）ac code:#include#include#include#includeusing namespace std;//#define inf 0xfffffff;const int maxn=99999999;int map_dis[1005][1005];bool vis[1005];int dis[1005];int t,n,m;int dijkstra(int s,int k){ memset(vis,false,sizeof(vis)); for(int i=1;i<=n;i++) dis[i]=map_dis[s][i]; dis[s]=0; vis[s]=true; for(int i=1;imaxx){ maxx=dis[j]; u=j; } } if(u==1)break; vis[u]=true; for(int g=1;g<=n;g++){ if(!vis[g]){ dis[g]=max(dis[g],min(dis[u],map_dis[u][g])); } } } return dis[k];}int main(){ scanf("%d",&t); for(int i=1;i<=t;i++){ memset(map_dis,0,sizeof(map_dis)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int b,e,v; scanf("%d%d%d",&b,&e,&v); //cout<

并且

给⼀些

有向边

判断这个图中有没有

负环

如果有

时光可以倒流//使⽤ bellman算法#include#include#includeconst int inf =0x3f3f3f3f;const int maxn = 6000;struct edge{ int b,e,v;}E[maxn];int dis [550];bool bellman(int s,int n,int nedge){ for(int i=1;i<=n;i++){ dis[i]=(i==s?0:inf); } for(int i=1;idis[E[j].b]+E[j].v) dis[E[j].e]=dis[E[j].b]+E[j].v; } } for(int g=1;g<=nedge;g++){ if(dis[E[g].e]>dis[E[g].b]+E[g].v){ return true; } } return false;}int main(){ int t,n,m,w,nnum; scanf("%d",&t); while(t--){ nnum=0; scanf("%d%d%d",&n,&m,&w); for(int i=1;i<=m;i++){ int bb,ee,vv; scanf("%d%d%d",&bb,&ee,&vv); E[++nnum].b=bb;E[nnum].e=ee; E[nnum].v=vv; E[++nnum].b=ee;E[nnum].e=bb; E[nnum].v=vv; } for(int j=1;j<=w;j++){ int bb,ee,vv; scanf("%d%d%d",&bb,&ee,&vv); E[++nnum].b=bb;E[nnum].e=ee; E[nnum].v=-vv; } if(bellman(1,n,nnum))printf("YESn"); else printf("NOn"); }}dijkstra + 优先队列优化：题⽬链接：ac code:#include#include#include#include#includeusing namespace std;const int maxn=110;const int maxv=10050;const int inf=0x3f3f3f3f;int vis[maxn];int dis[maxn];struct edge{ int u,v,w,next;}e[maxv];struct node{ int dist,num; friend bool operator < (node a,node b){ return >; }}p[maxn];int head[maxn];void init(){ memset(vis,0,sizeof(vis)); memset(dis,inf,sizeof(dis)); memset(head,-1,sizeof(head));}void dijkstra(int b){ priority_queueq; vis[b]=1; dis[b]=0; node now,temp; =dis[b]; =b; (now); while(!()){ now=(); (); vis[]=0; for(int i=head[];i!=-1;i=e[i].next){ if(dis[e[i].v]>dis[]+e[i].w){ dis[e[i].v]=dis[]+e[i].w; if(!vis[e[i].v]){ vis[e[i].v]=1; = dis[e[i].v]; = e[i].v; (temp); } } } }}int main(){ int n; int cnt=0; scanf("%d",&n); init(); for(int i=1;i#include#include#include#include#includeusing namespace std;const int maxn=50;const int maxv=2500;int vis[maxn];int visitcnt[maxn];double dis[maxn];struct edge { int u,v,next; double w;}e[maxv];struct node{ char s[50]; int num;}p[maxn];int head[maxn];void init(){ memset(vis,0,sizeof(vis)); memset(dis,0.0,sizeof(dis)); memset(visitcnt,0,sizeof(visitcnt));}bool spfa(int n,int b){ queueq; vis[b]=1; dis[b]=1; (b); while(!()){ int now=(); visitcnt[now]++; if(visitcnt[now]>n)return true; (); (); vis[now]=0; for(int i=head[now];i!=-1;i=e[i].next){ if(dis[e[i].v]