【日常学习】【最短路】几种常用最短路短发的总结比较

男娘i 2022-08-08 13:42 151阅读 0赞

学（fuxi）了一阵子简要总结一下

floyd 全跑一边 点的三次方 100以下都呛 与点有关 无关边数 （可用于求解最小环）  
dij裸 点的二次方 每次贪心取最小的松弛   
SPFA km k期望2 与边有关 稀疏图最好 搭配边表 最坏情况可能比上面的还慢 唯一可判负环  
Bellman-Ford SPFA复杂版 不考虑

dij优化 nlogn 与点有关 稠密图的最优解决方案

简而言之 稠密的图用dij的堆优化 稀疏的SPFA 很好写

代码汇总

floyd

//codevs1077 ¶àÔ´×î¶ÌÂ·
    //copyright by ametake
    #include
       
        
    #include
        
         
    using namespace std;
    
    const int maxn=0x3f3f3f3f;
    int a[101][101];
    
    int main()
    {
    	freopen("1.txt","r",stdin); 
    	int n;
    	scanf("%d",&n);
    	for (int i=0;i

`floyd传递闭包 //codevs1009 ²úÉúÊý NOIP2002ÆÕ¼° 
 //copyright by ametake
 #include           
 #include             
 using namespace std;
 
 int k,len;
 bool a[10][10];
 int w[50];
 char s[50];
 
 void init()
 {
 	freopen("1.txt","r",stdin);
 	scanf("%s%d",s,&k);//notice
 	len=strlen(s);
 	memset(a,false,sizeof(a));
 	int x,y;
 	for (int i=0;i               9) {w[i]+=w[i-1]/10;w[i-1]%=10;}
 	return;
 }
 
 void outit()
 {
 	int i=49;
 	while (w[i]==0) i--;//again!!!!!==
 	for (int j=i;j>0;j--) printf("%d",w[j]);
 	printf("\n");
 	return;
 }
 
 int main()
 {
 	init();
 	for (int k=0;k<=9;k++)
 	{
 		for (int i=0;i<=9;i++)
 		{
 			for (int j=0;j<=9;j++)
 			{
 				a[i][j]=a[i][j]||(a[i][k]&&a[k][j]);
 			}
 		}
 	}
 	memset(w,0,sizeof(w));
 	w[0]=w[1]=1;
 	for (int i=0;i                          dij //codevs1079 »Ø¼Ò Usaco dij
 //copyright by ametake
 #include             
 #include               
 using namespace std;
 
 const int maxn=101;
 const int maxdis=100000;
 const int last=52;
 int n;
 int dis[maxn],cost[maxn][maxn];
 bool vis[maxn];
 
 void init(){
 	scanf("%d",&n);
 	memset(vis,true,sizeof(vis));
 	memset(cost,-1,sizeof(cost));
 	for (int i=1;i<=51;i++) dis[i]=maxdis;
 	int d;
 	char a,b;
 	for (int i=0;i                 ='a'&&a<='z') a=a-'a'+1;
 		else a=a-'A'+27;
 		if (b>='a'&&b<='z') b=b-'a'+1;
 		else b=b-'A'+27;
 		if (a!=b){
 			if ((cost[a][b]==-1)||(d                   =1;j--) if (vis[j]&&dis[j]                     -1){ int temp=cost[minj][j]+dis[minj]; if (temp                                                   SPFA //codevs1021 ÂêÀö¿¨ SPFA+Êý×éÄ£ÄâÁÚ½Ó±í »ÆÑ§³¤Õý½â hzwer 
 #include               
 #include                 
 #include                   
 using namespace std;
 struct data{
 	int from,to,next,v;
 }e[1000001];
 int n,m,ans;
 int ne;
 int head[1001];
 bool inq[1001],del[1000001];
 int q[1000001],dis[1001],father[1001];
 void insert(int u,int v,int w)
 {
 	ne++;
 	e[ne].from=u;
 	e[ne].to=v;
 	e[ne].v=w;
 	e[ne].next=head[u];
 	head[u]=ne;
 }
 void spfa(int k)
 {
 	memset(dis,127,sizeof(dis));
 	memset(inq,0,sizeof(inq));
 	int t=0,w=1,now;
 	q[t]=1;inq[1]=1;dis[1]=0;
 	while(t                                  SPFA的SLF+LLL优化（这个代码不知为什么更慢了） //codevs1021 ÂêÀö¿¨ SPFA+SLF+LLLÓÅ»¯ 
 //copyright by ametake
 //first time to write SPFA&&edge deleted shortest road,HURRY UP! 
 #include                 
 #include                   
 #include                     
 using namespace std;
 
 /*struct node
 {
     friend bool operator< (node n1, node n2)
     {
         return n1.priority < n2.priority;
     }
     int priority;
     int value;
 };*/
 struct w
 {
 	int dist,num;
 	bool operator < (w n2)const
 	{
 		return dist                        q; 
 
 
 void init() 
 {
 	scanf("%d%d",&v,&e);
 	int a,b,d;
 	memset(map,0x3f,sizeof(map));
 	memset(pre,0,sizeof(pre));
 	for (int i=0;i                         node[u].dist+map[u][i]) { if ((u!=head)||(i!=tail)) { node[i].dist=node[u].dist+map[u][i]; pre[i]=u; if (!in[i]) q.push(node[i]); in[i]=true; } } } } res=node[v].dist; return; } void work() { spfa(); int i=v; int ans=0; int b[maxn]; memcpy(b,pre,sizeof(b)); do { head=b[i]; tail=i; //int temp=map[head][tail]; //map[head][tail]=0x3f3f3f3f; spfa(); if (res>ans) ans=res; //map[head][tail]=temp; i=head; }while (i!=1); //¶ÔÓÚÃ¿ÌõÔÚ×î¶ÌÂ·ÉÏµÄ±ß É¾±ß spfa //·µ»Ø³¤¶È ±È½Ï Ñ¡Ôñ×îÐ¡Öµ //Ñ»·½áÊøºó ·µ»Ø×îÐ¡Öµ printf("%d\n",ans); return; } int main() { freopen("1.txt","r",stdin); init(); work(); return 0; }                                                   dij堆优化最终版 //codevs2038 香甜的黄油 重写 邻接表+dij堆优化
 //邻接表 优先队列 挑战 加油！
 #include                 
 #include                   
 #include                     
 using namespace std;
 
 int oo ;
 struct data
 {
 	int v,w,next;
 }e[3001];//edge 终点，边权，下一条同源边 
 
 struct w
 {
 	int dist,num;
 	bool operator < (w n2)const
 	{
 		return dist>n2.dist;
 	}             
 }node[801];//每个node是一个点，有编号和dist 
 
 int ne,n,p,c,a,b,d;
 int head[801],cow[801];//head:edge from here;cow:the position of each cow;
 bool vis[801];
 int tot,ans;
 
 void insert(int &x,int &y,int &w)
 {
 	ne++;
 	e[ne].v=y;
 	e[ne].w=w;
 	e[ne].next=head[x];
 	head[x]=ne;
 } 
 
 void init()
 {
 	scanf("%d%d%d",&n,&p,&c);
 	memset(head,0,sizeof(head));
 	for (int i=1;i<=n;i++) scanf("%d",&cow[i]);//from 1!
 	for (int i=1;i<=c;i++)
 	{
 		scanf("%d%d%d",&a,&b,&d);
 		insert(a,b,d);
 		insert(b,a,d);
 	}
 }
 
 void dij(int &k)
 {
 	priority_queue                        q;
 	node[k].dist=0;
 	q.push(node[k]);
 	int disj,minj;//dis of j and number of j
 	while (!q.empty()) 
 	{
 		minj=q.top().num;
 		disj=q.top().dist;
 		vis[minj]=true;
 		q.pop();
 	    int pi=head[minj];
 	    while (pi)
 	    {
 	    	if (!(vis[e[pi].v]) && (disj+e[pi].w < node[e[pi].v].dist || disj == oo))
 	    	    {node[e[pi].v].dist=disj+e[pi].w;q.push(node[e[pi].v]);}
 	    	pi=e[pi].next;
 		}
 	}
 	//首先循环一边找出dist最小的点
 	//然后循环一边对于每个点以dist为中间点更小就更新dist 
 	//从当前dist连着的边里找 
 	tot=0;
 	for (int i=1;i<=n;i++) tot+=node[cow[i]].dist;//结果反馈：与K直接连着的边正常，不直接相连的正无穷未更新 
 	return;
 }
 
 int main()
 {
 	freopen("1.txt","r",stdin);
 	int inf = 0x3f3f3f3f;
 	oo = inf;
 	init();
 	ans=0x3f3f3f3f;
 	for (int i=1;i<=p;i++) node[i].num=i;
 	for (int i=1;i<=p;i++)
 	{
 		memset(vis,false,sizeof(vis));
 		for (int j=1;j<=p;j++) 
 		{
 		    node[j].dist=0x3f3f3f;
 		}
 	    dij(i);if (tot                                                  ——孤城暮角，引胡笳怨。`