The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

倾情奉献系列之最短路系列(POJ)

第一部分 Dijkstra 算法


POJ 2387 ——Til the Cows Come Home
最典型的最短路题目,求两点间的最短路径,一次Dij即可,代码如下:



#include
<iostream>
#include
<cmath>
#include
<cstdio>
#include
<algorithm>
using namespace std;

#define MAX_INTEGER  0x7fffffff


int n;
int const MAX=2000;
int value[MAX][MAX];
bool visit[MAX];
int dis[MAX];

int dijkstra()
{
    memset(visit,
false,sizeof(visit));

    
int i;
    
int j;


    
for(i=1;i<=n;i++)
    
{
        dis[i]
=value[n][i];
        visit[i]
=false;
    }

    value[n][n]
=0;

    dis[n]
=0;visit[n]=true;
    
for(i=1;i<n;i++)
    
{
        
int mark_num=n;
        
int mark_dis=MAX_INTEGER;
        
int temp=MAX_INTEGER;
        
for(j=1;j<=n;j++)
        
{
            
if(!visit[j]&&dis[j]<temp)
            
{
                mark_num
=j;
                temp
=dis[j];
                
            }

        }

        visit[mark_num]
=true;
        
for(j=1;j<=n;j++)
        
{
            
if((!visit[j])&&(value[mark_num][j]<MAX_INTEGER))
            
{
                
int newdis=dis[mark_num]+value[mark_num][j];
                
if(newdis<dis[j])
                
{
                    dis[j]
=newdis;
                }

            }

        }

    }

    
return dis[1];
}


int main ()
{
    
int t;
    
int i,j;

    
while(    scanf("%d%d",&t,&n)!=EOF)
    
{
        
for(i=1;i<=n;i++)
        
{
            
for(j=1;j<=n;j++)
            value[i][j]
=MAX_INTEGER;
        }

        
for(i=1;i<=t;i++)
        
{
            
int a,b,len;
            scanf(
"%d%d%d",&a,&b,&len);
            
if(len<value[a][b])
            
{
                value[a][b]
=len;
                value[b][a]
=len;
            }


        }

        cout
<<dijkstra()<<endl;
    }

    
return 0;
}




POJ 2253——Frogger
Dij的变形,这道题目的意思大致是,给你起点和终点,还有一些可用来中间过度的点,首先保证你能够跳跃到终点,同时还要保证你的跳跃跨度最小,也就是从起点到终点路径上的最大的那条边要尽量小,这个有点绕,所以我把这道题目改一下^_^:

等价题:假设你在玩一个闯关游戏,目的是到达终点闯关,走哪条路无关紧要,你把那些点之间的路径看成是怪物,路径长度看成是怪物的能量值,如果你想击败怪物顺利闯关的话,你的能量值必须高于怪物的能量值,当然获得能量值是需要付出代价的,现在你想用最少的代价通关,求这个最小的能量值是多少?


不难想到,此题可以用Dij来解,只需要把sum改成max即可。不得不提的是,这里不是求最短路径,而是求连通图的最小边的问题,它们都可以用Dij,个人感觉它们似乎是平行的关系,只不过是Dij大环境下的2个变种罢了。在最短路径问题中,dis[i]数组中存储的是,i点到原点的最小距离,而在连通图最小边问题中,dis[i]数组中存储的是i点到周围任何一个点的最小距离(当然这个距离是通过不断的松弛,最后才得到的^_^)
代码如下:

#include<iostream>
#include
<cmath>
#include
<cstdio>
#include
<algorithm>
using namespace std;

#define MAX_NUMBER  0x7fffffff

double len(int a,int b,int c,int d)
{
    
return sqrt((double)((a-c)*(a-c)+(d-b)*(d-b)));
}



struct dot
{
    
int x;
    
int y;
}
dotset[201];





int n;
int const MAX=201;
double record[MAX];
double value[MAX][MAX];
bool visit[MAX];
double dis[MAX];

double dijkstra()
{
    
double max_step=0;
    memset(visit,
false,sizeof(visit));
    
    
int i;
    
int j;
    
for(i=1;i<=n;i++)
    
{
        dis[i]
=value[1][i];
        visit[i]
=false;
    }

    
    dis[
1]=0;visit[1]=true;
    
for(i=1;i<n;i++)
    
{
        
        
int mark_num=1;
        
double temp=MAX_NUMBER;
        
for(j=1;j<=n;j++)
        
{
            
if(!visit[j]&&dis[j]<temp)
            
{
                
                mark_num
=j;
                temp
=dis[j];
            }

            
        }

        
if(temp>max_step)
            max_step
=temp;
        
if(mark_num==2)
            
return max_step;
        visit[mark_num]
=true;
        
        
for(j=1;j<=n;j++)
        
{
            
if((!visit[j]))
            
{
                
double newdis=value[mark_num][j];
                
if(newdis<dis[j])
                
{
                    dis[j]
=newdis;
                }

            }

        }

    }

}


int main ()
{
    
int i,j,k;
    
    
for(k=1;;k++)
    
{
        scanf(
"%d",&n);
        
if(n==0)
            
break;
        
for(i=1;i<=n;i++)
        
{
            scanf(
"%d %d",&dotset[i].x,&dotset[i].y);
        }

        
for(i=1;i<=n;i++)
        
{
            
for(j=1;j<=n;j++)
            
{
                value[i][j]
=len(dotset[i].x,dotset[i].y,dotset[j].x,dotset[j].y);
            }

        }

        printf(
"Scenario #%d\nFrog Distance = %.3f\n\n",k,dijkstra());
    }

    
return 0;
}



POJ 1797——Heavy Transportation
还是最短路,与frogger正好相反,求的是连通图最小边的问题,可以与上一题对应起来看。

#include<iostream>
#include
<cmath>
#include
<cstdio>
#include
<algorithm>
using namespace std;
#define MAX 1001
#define MIN_NUMBER  0





int n;
int     value[MAX][MAX];
bool visit[MAX];
int dis[MAX];

int dijkstra()
{
    
int max_weight=1000001;
    memset(visit,
false,sizeof(visit));

    
int i;
    
int j;
    
for(i=1;i<=n;i++)
    
{
        value[i][i]
=0;
        dis[i]
=value[1][i];
        visit[i]
=false;
        
    }


    dis[
1]=0;visit[1]=true;
    
for(i=1;i<n;i++)
    
{
        
        
int mark_num=1;
        
int temp=MIN_NUMBER;
        
for(j=1;j<=n;j++)
        
{
            
if(!visit[j]&&dis[j]>temp)
            
{
                
                mark_num
=j;
                temp
=dis[j];

                
            }

            
        }

        
if(temp<max_weight)
            max_weight
=temp;
        
if(mark_num==n)
            
return max_weight;
        visit[mark_num]
=true;
        
        
for(j=1;j<=n;j++)
        
{
            
if((!visit[j])&&value[mark_num][j]!=MIN_NUMBER)
            
{
                
int newdis=value[mark_num][j];
                
if(newdis>dis[j])
                
{
                    dis[j]
=newdis;
                }

            }

        }



        
    }

    


}


int main ()
{
    
int i,j,k;
    
int m;
    
int testcase;
    scanf(
"%d",&testcase);
    
for(k=1;k<=testcase;k++)
    
{
        scanf(
"%d %d",&n,&m);
        
for(i=1;i<=n;i++)
        
{
            
for(j=1;j<=n;j++)
            
{
                value[i][j]
=MIN_NUMBER;
            }

        }



    
        
for(i=1;i<=m;i++)
        
{
            
int a,b,len;
            scanf(
"%d %d %d",&a,&b,&len);
            
if(len>value[a][b])
            
{
                value[a][b]
=len;
                value[b][a]
=len;
            }

        }

        printf(
"Scenario #%d:\n%d\n\n",k,dijkstra());
    }

    
return 0;
}


POJ 3268——
Silver Cow Party
正反两次使用Dijkstra算法即可

#include<iostream>
#include
<cmath>
#include
<cstdio>
#include
<algorithm>
using namespace std;

#define MAX 1005
#define MAX_NUM 0x7fffffff

int n;
int valuecome[MAX][MAX];
int valueback[MAX][MAX];
int dis[MAX];
bool visit[MAX];
int record[MAX];




void dijkstra(int x)
{
    
int temp=MAX_NUM;
    
int i;
    
int j;
    
int mark;
    memset(visit,
false,sizeof(visit));
    
for(i=1;i<=n;i++)
    
{
        valuecome[i][i]
=0;
        dis[i]
=valuecome[x][i];
    }

    dis[x]
=0;
    visit[x]
=true;
    
for(i=1;i<n;i++)
    
{
        temp
=MAX_NUM;
        mark
=x;
        
for(j=1;j<=n;j++)
        
{
            
if(!visit[j]&&dis[j]<temp)
            
{
                temp
=dis[j];
                mark
=j;
            }

        }

        visit[mark]
=true;
        
for(j=1;j<=n;j++)
        
{
            
if((!visit[j])&&(valuecome[mark][j]<MAX_NUM))
            
{
                
int newdis=dis[mark]+valuecome[mark][j];
                
if(newdis<dis[j])
                
{
                    dis[j]
=newdis;
                }

            }

        }

    }

}


void dijkstra2(int x)
{
    
int temp=MAX_NUM;
    
int i;
    
int j;
    
int mark;
    memset(visit,
false,sizeof(visit));
    
for(i=1;i<=n;i++)
    
{
        valueback[i][i]
=0;
        dis[i]
=valueback[x][i];
    }

    dis[x]
=0;
    visit[x]
=true;
    
for(i=1;i<n;i++)
    
{
        temp
=MAX_NUM;
        mark
=x;
        
for(j=1;j<=n;j++)
        
{
            
if(!visit[j]&&dis[j]<temp)
            
{
                temp
=dis[j];
                mark
=j;
            }

        }

        visit[mark]
=true;
        
for(j=1;j<=n;j++)
        
{
            
if((!visit[j])&&(valueback[mark][j]<MAX_NUM))
            
{
                
int newdis=dis[mark]+valueback[mark][j];
                
if(newdis<dis[j])
                
{
                    dis[j]
=newdis;
                }

            }

        }

    }

}



int main ()
{

    
int m,x;
    
int i,j;
    
int u,v,len;
    scanf(
"%d%d%d",&n,&m,&x);
    
for(i=1;i<=n;i++)
    
{
        
for(j=1;j<=n;j++)
        
{
            valuecome[i][j]
=MAX_NUM;
            valueback[i][j]
=MAX_NUM;
        }

    }

    



    
for(i=1;i<=m;i++)
    
{
        scanf(
"%d%d%d",&u,&v,&len);
        
if(len<valuecome[u][v])
        
{
            valuecome[u][v]
=len;
            valueback[v][u]
=len;
        }

    }

    dijkstra(x);
    
for(i=1;i<=n;i++)
    
{
        record[i]
+=dis[i];
    }


    dijkstra2(x);
    
for(i=1;i<=n;i++)
    
{
        record[i]
+=dis[i];
    }

    
int max=0;
    max
=0;
    
for(i=1;i<=n;i++)
    
{
        
if(record[i]>max&&i!=x)
            max
=record[i];
    }

    printf(
"%d\n",max);

    
return 0;

}




第二部分 Bellman-Ford算法

POJ 1860——Currency Exchange

Bellman_Ford的经典变形。。。精度很重要

#include<stdio.h>
#include
<memory.h>
struct node
{
  
int u,v;
  
double r,c;
}
;
int n,m,s;
double val;
node edge[
1001];
int eg;

bool bellman()
{
  
double dist[102];
  memset(dist,
0,sizeof(dist));
  
int i;
  
int k;
  
int flag = 0;
  dist[s] 
= val;
  
while(dist[s]<=val)
  
{
    flag  
= 0;
    
for(i = 0;i<=eg;i++)
    
{
      
if(dist[edge[i].v]<(dist[edge[i].u]-edge[i].c)*edge[i].r)
      
{
        dist[edge[i].v] 
= (dist[edge[i].u]-edge[i].c)*edge[i].r;
        flag
=1;
      }

    }

    
if(!flag)
      
return dist[s]>val;
  }

  
return true;
}

int main()
{
  
int i;
  
int a,b;
  
double rab, cab, rba ,cba;
  
while(scanf("%d %d %d %lf",&n,&m,&s,&val)!=EOF)
  
{
    eg  
= 0;
    
for(i = 0;i<m;i++)
    
{
      scanf(
"%d %d %lf %lf %lf %lf",&a,&b,&rab,&cab,&rba,&cba);
      edge[eg].u 
= a;
      edge[eg].v 
= b;
      edge[eg].r 
= rab;
      edge[eg].c 
= cab;
      eg
++;
      edge[eg].u 
= b;
      edge[eg].v 
= a;
      edge[eg].r 
= rba;
      edge[eg].c 
= cba;
      eg
++;
    }

    
if(bellman())
    
{
      printf(
"YES\n");
    }

    
else
    
{
      printf(
"NO\n");
    }

  }

  
return 0;
}




POJ 3259——Wormholes(寻找负权回路)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3259
题意 : 一个famer有一些农场,这些农场里面有一些田地,田地里面有一些虫洞,田地和田地之间有路,虫洞有这样的性质: 时间倒流。问你这个农民能不能看到他自己,也就是说,有没有这样一条路径,能利用虫洞的时间倒流的性质,让这个人能在这个点出发前回去,这样他就是能看到他自己


通常情况下图中的边权都为正数,这个时候可以用Dij算法,但有的时候图中的边权会为负值,这时候Dij算法便失去它的作用了,此时可以用Bellman算法,值得一提的是我们通常不用bellman算法来求最短路径,寻找负权回路才是Bellman算法最主要的应用领域(负权回路是指边权之和为负数的环)
这道题目的大意是让你判断给出的图中是不是有负权回路。此时Bellman便大显神威了:-)



#include<iostream>
#include
<cmath>
#include
<algorithm>
using namespace std;

#define MAX 501
#define MAX_NUM 10001
struct node
{
    
int u;
    
int v;
    
int w;
}
edge[5500];


int n;
int m;
int w;

int dis[MAX];

bool bellman ()
{
    
int i,j;
    
for(i=1;i<=n;i++)
    
{
        dis[i]
=MAX_NUM;
        
    }

    dis[
1]=0;
    
for(i=1;i<=n-1;i++)
    
{
        
for(j=1;j<=2*m+w;j++)
        
{
            
if(dis[edge[j].v]>dis[edge[j].u]+edge[j].w)
                dis[edge[j].v]
=dis[edge[j].u]+edge[j].w;
        }

    }

    
for(i=1;i<=2*m+w;i++)
    
{
        
if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w)
            
return false;
    }

    
return true;
}




int main ()
{
    
int testcase;
    scanf(
"%d",&testcase);
    
int pos=0;
    
int i,j,k;

    
for(i=1;i<=testcase;i++)
    
{
        pos
=0;
        scanf(
"%d%d%d",&n,&m,&w);
        
for(j=1;j<=m;j++)
        
{
            pos
++;
            scanf(
"%d%d%d",&edge[pos].u,&edge[pos].v,&edge[pos].w);
            pos
++;
            edge[pos].v
=edge[pos-1].u;
            edge[pos].u
=edge[pos-1].v;
            edge[pos].w
=edge[pos-1].w;

        }

        
for(j=1;j<=w;j++)
        
{
            pos
++;
            scanf(
"%d%d%d",&edge[pos].u,&edge[pos].v,&edge[pos].w);
            edge[pos].w
=-edge[pos].w;
            
        }

        
if(bellman())
            printf(
"NO\n");
        
else
            printf(
"YES\n");
    }

    
return 0;
}





            


第三部分 Floyd 算法

POJ 1502——MPI Maelstrom
就是要求出源点到其他各点的最短路,然后在求出最大值,由于点的数目很小,可以直接使用floyd,代码十分简洁。

#include<iostream>
#include
<cmath>
#include
<cstdio>
#include
<algorithm>
using namespace std;
#define maxint 1000000000

int value[101][101];
char test[100];

bool isdigit(char test[])
{
    
if(test[0]!='x')
        
return true;
    
else
        
return false;
}



int main ()
{
    
    
int temp;
    
int i,j,k;
    
int n;


    
while(cin>>n)
    
{
        
for(i=1;i<=n;i++)
            value[i][i]
=0;

        
for(i=2;i<=n;i++)
        
{
            
for(j=1;j<=i-1;j++)
            
{
                cin
>>test;
                
if(isdigit(test))
                
{
                    sscanf(test,
"%d",&temp);
                    value[i][j]
=temp;
                    value[j][i]
=temp;
                }

                
else
                
{
                    value[i][j]
=maxint;
                    value[j][i]
=maxint;
                }

            }

        }

        
for(k=1;k<=n;k++)
        
{
            
for(i=1;i<=n;i++)
            
{
                
for(j=1;j<=n;j++)
                
{
                    
if(value[i][k]!=maxint&&value[k][j]!=maxint)
                    
{

                        
if(value[i][k]+value[k][j]<value[i][j])
                            value[i][j]
=value[i][k]+value[k][j];
                    }

                }

            }

        }

        
int max=0;
        
for(i=2;i<=n;i++)
        
{
            
if(value[1][i]>max)
                max
=value[i][1];
        }

        
        cout
<<max<<endl;
    }

        
    
return 0;
}







POJ 3660——传递闭包
这道题是一道关于floyd的图论题。题目的意思是说有n头牛比赛,m种比赛结果,最后问你一共有多少头牛的排名被确定了,其中如果a战胜b,b战胜c,则也可以说a战胜c,即可以传递胜负。这样如果一头牛的被x头牛打败,打败y头牛,且x+y=n-1,则我们容易知道这头牛的排名就被确定了,所以我们只要将任何两头牛的胜负关系确定了,在遍历所有牛判断一下是否满足x+y=n-1,将满足这个条件的牛数目加起来就是所求解。

#include<iostream>
#include
<cmath>
using namespace std;

int map[101][101]={0};


int main ()
{
    
int n,m;
    scanf(
"%d %d",&n,&m);
    
int i,j,k;
    
for(i=1;i<=m;i++)
    
{
        
int a,b;
        scanf(
"%d %d",&a,&b);
        map[a][b]
=1;
    }

    
for(k=1;k<=n;k++)
    
{
        
for(i=1;i<=n;i++)
        
{
            
for(j=1;j<=n;j++)
            
{
                
if(map[i][k]==1&&map[k][j]==1)
                    map[i][j]
=1;
            }

        }

    }

    
int ans=0;
    
int temp=0;
    
for(i=1;i<=n;i++)
    
{
        temp
=0;
        
for(j=1;j<=n;j++)
        
{
            
if(j==i)
                
continue;
            
else if(map[i][j]==1||map[j][i]==1)
                temp
++;
        }

        
if(temp==n-1)
            ans
++;
    }

    cout
<<ans<<endl;
return 0;
}







 

POJ 2240——Arbitrage
这就是个套汇的问题,可以用Floyd求最大环,然后判断是不是大于1。

#include <cstdio>
#include 
<string>
#include 
<map>
using namespace std;

map
<string,int> MAP;
double value[31][31];
double rate;
double tempfloat;

int main()
{
    
int i,j,k,n,m;
    
int count=1;
    
char temp[100],temp1[100];
    
while(scanf("%d",&n))
    
{
        
if(n==0)
            
break;
        MAP.clear();
        memset(value,
0,sizeof(value));
        
for(i=1;i<=n;i++)
        
{
            scanf(
"%s",temp);
            MAP[(
string)temp]=i;
        }

        scanf(
"%d",&m);
        
for(i=1;i<=m;i++)
        
{
            scanf(
"%s %lf %s",temp,&rate,temp1);
            value[MAP[(
string)temp]][MAP[(string)temp1]]=rate;
        }

        
for(k=1;k<=n;k++)
          
for(i=1;i<=n;i++)
            
for(j=1;j<=n;j++)
            
{
                tempfloat
=value[i][k]*value[k][j];
                
if(tempfloat>value[i][j])
                        value[i][j]
=tempfloat;
            }

        
for(i=1;i<=n;i++)
            
if(value[i][i]>1)
            
{
                printf(
"Case %d: Yes\n",count++);
                
break;
            }

        
if(i==n+1)
        printf(
"Case %d: No\n",count++);
    }

}

 

第四部分 SPFA 算法(Shortest Path Faster Algorithm)

POJ 1511——Invitation Cards
顾名思义,SPFA算法的特点就是快,这道题用之前的任何算法均会超时,只有使用SPFA算法才能AC,可见SPFA算法的优越性^_^

//Coded by abilitytao 
//Time:2009-04-10 22:49:58
#include<iostream>
#include
<cmath>
#include
<queue>
using namespace std;
#define MAX_NUM 1000000001
#define MAX_DOTNUM 1000001

int n,m;
queue
<int>myqueue;
bool mark[MAX_DOTNUM];
__int64 dis[MAX_DOTNUM];


struct node
{

    
int v;
    
int w;
    node 
*next;
}
edge[MAX_DOTNUM];//此邻接表用于存储正向图

node reversed_edge[MAX_DOTNUM];
//此逆邻接表用于存储逆向图

void initial(node edge[])//邻接表的初始化,里面封装了回收上一次操作所分配之内存的操作
{
    
int i;
    node 
*p;
    node 
*q;
    
for(i=1;i<=n;i++)
    
{
        p
=&edge[i];
        q
=p->next;
        
while(q!=NULL)
        
{
            p
->next=q->next;
            delete q;
            q
=p->next;
        }

    }

}



void input_case()//每一个case的输入函数
{

    
int i;
    
for(i=1;i<=m;i++)
    
{
        node 
*p;
        node 
*q;
        
int a,b,c;
        scanf(
"%d%d%d",&a,&b,&c);
        
/**/////////////////////////
        p=&edge[a];
        q
=new node;
        q
->v=b;
        q
->w=c;
        q
->next=p->next;
        p
->next=q;
        
/**/////////////////////////
        p=&reversed_edge[b];
        q
=new node;
        q
->v=a;
        q
->w=c;
        q
->next=p->next;
        p
->next=q;
    }

}



void spfa(node edge[])//SPFA部分
{

    
int i;
    
/**////////////////////////////////////////////////////////////////
    memset(mark,false,sizeof(mark));
    
for(i=1;i<=n;i++)
        dis[i]
=MAX_NUM;
    
while(myqueue.size()!=0)
        myqueue.pop();
    
/**////////////////////////////////////////////////////////////
    dis[1]=0;
    mark[
1]=true;
    myqueue.push(
1);
    
while(myqueue.size()!=0)//如果队列不空,则进行松弛操作,直到队列空为止
    {
        
int temp=myqueue.front();
        myqueue.pop();
        mark[temp]
=false;
        node 
*p;
        
for(p=edge[temp].next;p!=NULL;p=p->next)
        
{
            
if(dis[p->v]>dis[temp]+p->w)
            
{
                dis[p
->v]=dis[temp]+p->w;
                
if(mark[p->v]!=true)
                
{
                    myqueue.push(p
->v);
                    mark[p
->v]=true;
                }

            }

        }

    }

}



int main()
{

    
int testcase;
    
int i,j;
    __int64 sum;
    scanf(
"%d",&testcase);
    
for(i=1;i<=MAX_DOTNUM-1;i++)
    
{
        edge[i].v
=i;
        edge[i].w
=0;
        edge[i].next
=NULL;
    }

    
for(i=1;i<=MAX_DOTNUM-1;i++)
    
{
        reversed_edge[i].v
=i;
        reversed_edge[i].w
=0;
        reversed_edge[i].next
=NULL;
    }

    
for(i=1;i<=testcase;i++)
    
{
        sum
=0;
        scanf(
"%d%d",&n,&m);
        initial(edge);
        initial(reversed_edge);
        input_case();
        spfa(edge);
        
for(j=1;j<=n;j++)
            sum
+=dis[j];
        spfa(reversed_edge);
        
for(j=1;j<=n;j++)
            sum
+=dis[j];
        printf(
"%I64d\n",sum);
    }

    system(
"pause");
    
return 0;

}

再次看这个题目,发现以前的代码风格实在是太差了,同样的题目,现在写只要91行。。。。。。。。。。。。。。。。。。。。。。。。

#include<iostream>
#include
<algorithm>
#include
<queue>
#include
<cstdio>
using namespace std;

#define bint long long 

int const maxn=1000000;
int const maxm=2000000;
int const INF=1000000000;

struct node
{
    
int t,w;
    node 
*next;
}
edge[maxm],*adj[maxn],*nadj[maxn];
int len=0;
void init(int n){
    
for(int i=0;i<n;i++){adj[i]=NULL;nadj[i]=NULL;}
    len
=0;
}


void addedge(node *adj[],int u,int v,int w){
    edge[len].t
=v;edge[len].w=w;edge[len].next=adj[u];adj[u]=&edge[len++];
}

void insert(int u,int v,int w)
{
    addedge(adj,u,v,w);
    addedge(nadj,v,u,w);
}


int use[maxn];
bint dis[maxn];
queue
<int>Q;
bint SPFA(node 
*adj[],int n,int s,int t)
{
    
while(!Q.empty())Q.pop();fill(use,use+n,0);fill(dis,dis+n,INF);
    Q.push(s);use[s]
=1;dis[s]=0;
    
while(!Q.empty())
    
{
        
int t=Q.front();Q.pop();use[t]=0;
        
for(node *p=adj[t];p;p=p->next){
            
if(dis[t]+p->w<dis[p->t]){
                dis[p
->t]=dis[t]+p->w;
                
if(!use[p->t]){
                    use[p
->t]=1;
                    Q.push(p
->t);
                }

            }

        }

    }

    
if(dis[t]==INF)return -1;
    
else return dis[t];
}



int main()
{
    
int ca;
    scanf(
"%d",&ca);
    bint sum;
    
while(ca--)
    
{
        
        sum
=0;
        
int n,m;
        scanf(
"%d%d",&n,&m);
        init(n);
        
for(int i=0;i<m;i++)
        
{
            
int a,b,c;
            scanf(
"%d%d%d",&a,&b,&c);
            insert(a
-1,b-1,c);
        }

        SPFA(adj,n,
0,n-1);
        
for(int i=0;i<n;i++)
            sum
+=dis[i];
        SPFA(nadj,n,
0,n-1);
        
for(int i=0;i<n;i++)
            sum
+=dis[i];
        printf(
"%lld\n",sum);
    }

    
return 0;
}






特别感谢 :WinterLegend
2009年7月7日21:20:31

posted on 2009-07-07 15:39 abilitytao 阅读(5194) 评论(12)  编辑 收藏 引用

评论

# re: 倾情奉献系列之最短路系列(POJ)[正在编辑中...] 2009-07-08 21:09 zhouxi

我学的是C#但对这个还是不了解。看了那么多久代码挺乱的。
大哥,我真的像你好好学习。
我的邮箱:zhouxi04@yahoo.com.cn;
这是我的邮箱以后大家多交流。  回复  更多评论   

# re: 倾情奉献系列之最短路系列(POJ)[正在编辑中...] 2009-07-08 22:00 Huanglei

实在是佩服,虽说我考研时,看了,也朦朦懂一些这几个算法,但是让我编出来,您我偶像!  回复  更多评论   

# re: 倾情奉献系列之最短路系列(POJ) 2009-09-17 13:44 nobody

我怎么感觉你那个bellman-ford的poj1860题其并没有太多的bellman-ford的思想在里面呢?希望能和你交流  回复  更多评论   

# re: 倾情奉献系列之最短路系列(POJ)[未登录] 2009-10-31 11:29 cici

@nobody
就形式不一样,思想上是一样的,一样是枚举所有点收缩  回复  更多评论   

# re: 倾情奉献系列之最短路系列(POJ) 2009-10-31 13:35 abilitytao

@cici
正解  回复  更多评论   

# re: 倾情奉献系列之最短路系列(POJ) 2010-06-06 12:14 wzhgba

一切皆SPFA  回复  更多评论   

# re: 倾情奉献系列之最短路系列(POJ) 2010-06-06 15:58 tt

@wzhgba
多点间的最短路没法用spfa吧。。。  回复  更多评论   

# re: 倾情奉献系列之最短路系列(POJ) 2010-09-24 13:43 jince

第二题dis[]定义好像不对!应该是到i点所有路径的最大边最小的值!函数写的也不对!但是交上去怎么能过呢!  回复  更多评论   

# re: 倾情奉献系列之最短路系列(POJ)[未登录] 2010-09-24 19:06 abilitytao

@jince
我看看  回复  更多评论   

# re: 倾情奉献系列之最短路系列(POJ) 2010-09-26 14:32 jince

@abilitytao
看出来没?网上群搜下!  回复  更多评论   

# re: 倾情奉献系列之最短路系列(POJ) 2010-09-26 18:20 abilitytao

@jince
刚才我看了下 其实这题是个prim嘛 可能去年做的时候想烦了 因为DIj和prim确实比较相似
网上有一种并查集的解法 不知道你看了没?其实用prim和并查集的思想是一样的.  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理