【日常学习】【SPFA负环+数组模拟链表实现】codevs2645 Spore题解

客官°小女子只卖身不卖艺 2022-08-08 13:42 84阅读 0赞

之前刚刚写了一道“香甜的黄油”，是USACO的经典题目了。那道题用SPFA怎么找都过不了，看着别人的PAS轻松过各种拙计。黄学长说最佳方案应当是堆优化的dij，我还没有血，等学了那个之后再写黄油题解吧。

题目：

题目描述 Description

在星系1 的某颗美丽的行星之上.某陈将去标号为N 的星系,从星系g1 到达g2,某陈需要花费c1 的代价\[主要是燃料,另外还有与沿途Grox 的势力作战的花费\],c1 小于0 则是因为 这样的星系旅行,会给某陈带来收益\[来源于物流差价,以及一些殖民地的税收..\].相应地,c2 则是代表从星系g2 到达g1 的代价.据某陈了解,共有M 条这样的星系间路径. 为了战备,他需要选择一条总代价最小的路线.

输入描述 Input Description

输入文件包括多组数据. 对于每一组数据,第一行有2 个整数n,m,如题目描述中的含义,1<=n<=1000,0<=m<=10000. 接下来的m 行,每行会有四个整数g1,g2,c1,c2,如题目描述中的含义.0<=g1,g2<=n.输入数据保证所有整数都在\[- 10000..10000\]的范围内. n=0,m=0 标识着输入数据的结束.每个输入文件包含不超过10 组数据.

输出描述 Output Description

对于每组输入数据,输出一行,为从星系1 到星系N 的最小代价的路线的代价. 如果这样的路线不存在,输出'No such path'.

样例输入 Sample Input

3 2 1 2 2 -1 2 3 0 1 0 0

样例输出 Sample Output

题目的描述好长，去了没用的部分。

那么，关于这道题，我是第一次写数组模拟链表实现，对于SPFA而言的确提高不少效率，如果加上SLF和LLL可能会效率更高（需要写一个优先队列+结构体并重载定义比较函数）。负环的判断，只要加一个数组就可以了，因为最坏的情况是对于这个点，所有点都会改变，都会松弛这个点，最多松弛n次，就是入队n次。如果进队次数>n，那么一定是出现了负环，一直沿着负环走最短路可以无穷小，因此不存在最短路。

放代码

//codevs2645 Spore SPFA有负环+数组模拟链表
    //copyright by ameatke
    //first time to right link graph,cheer up!
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    int m,n,g1,g2,c1,c2;
    int et,head[20001],ld[20001],next[20001],val[20001];
    int dis[1001],cnt[1001],inq[1001],flag;
    //队列中存的是待松弛的点，head存的是以这个点为起点的第一条编的编号
    //next存的是同起点边序列的下一条编的编号
    //p是边的编号，每一次从同起点序列的第一条边开始向后遍历，直到next[p]==0说明这是最后一条边 
    
    void insert(int &a,int &b,int &c) 
    {
    	et++;//et is the number of edge
    	ld[et]=b;
    	val[et]=c;
    	next[et]=head[a];//next edge point to the first edge who has the same start,the last next is 0
    	head[a]=et;//turn the first edge to now edge,also a number
    }  
    
    void spfa()
    {
    	queue
          
            q;
    	int p;
    	dis[1]=0;
    	inq[1]=1;
    	cnt[1]=1;
    	q.push(1);
    	while (!q.empty())
    	{
    		p=head[q.front()];//p is the number of the first edge whose start is a
    		while (p)
    		{
    			if (dis[q.front()]+val[p]
           
            n) { printf("No such path\n");flag=1;return; } if (!inq[ld[p]]) { inq[ld[p]]++; q.push(ld[p]); } } p=next[p]; } inq[q.front()]=0; q.pop(); } return; } int main() { while (scanf("%d%d",&n,&m)&&n) { flag=0;et=0; memset(next,0,sizeof(next)); memset(head,0,sizeof(head)); memset(cnt,0,sizeof(cnt)); memset(inq,0,sizeof(inq)); memset(dis,0x3f,sizeof(dis)); for (int i=0;i

`这个很重要，今后也要经常翻看学习 ——一道残阳铺水中，半江瑟瑟半江红。`