【日常学习】【SPFA+SLF+LLL】codevs1021 玛丽卡题解

痛定思痛。 2022-08-08 11:58 119阅读 0赞

题目描述 Description

麦克找了个新女朋友，玛丽卡对他非常恼火并伺机报复。

因为她和他们不住在同一个城市，因此她开始准备她的长途旅行。

在这个国家中每两个城市之间最多只有一条路相通，并且我们知道从一个城市到另一个城市路上所需花费的时间。

麦克在车中无意中听到有一条路正在维修，并且那儿正堵车，但没听清楚到底是哪一条路。无论哪一条路正在维修，从玛丽卡所在的城市都能到达麦克所在的城市。

玛丽卡将只从不堵车的路上通过，并且她将按最短路线行车。麦克希望知道在最糟糕的情况下玛丽卡到达他所在的城市需要多长时间，这样他就能保证他的女朋友离开该城市足够远。

编写程序，帮助麦克找出玛丽卡按最短路线通过不堵车道路到达他所在城市所需的最长时间(用分钟表示)。

输入描述 Input Description

第一行有两个用空格隔开的数N和M，分别表示城市的数量以及城市间道路的数量。1≤N≤1000，1≤M≤N\*(N-1)/2。城市用数字1至N标识，麦克在城市1中，玛丽卡在城市N中。

接下来的M行中每行包含三个用空格隔开的数A，B和V。其中1≤A，B≤N，1≤V≤1000。这些数字表示在A和城市B中间有一条双行道，并且在V分钟内是就能通过。

输出描述 Output Description

输出文件的第一行中写出用分钟表示的最长时间，在这段时间中，无论哪条路在堵车，玛丽卡应该能够到达麦克处，如果少于这个时间的话，则必定存在一条路，该条路一旦堵车，玛丽卡就不能够赶到麦克处。

样例输入 Sample Input

5 7

1 2 8

1 4 10

2 3 9

2 4 10

2 5 1

3 4 7

3 5 10

样例输出 Sample Output

玛丽卡。

这道题目耗费了鄙人，恩，目前应该是九个小时了TUT从早上八点到下午五点，说起来都是泪啊TUTTUTTUTTUTTUTTUTTUTTUT眼泪哗哗流

因为一开始不大会写数组模拟的邻接表，也不想写链表，看有神奇的孩子Pascal邻接矩阵+dij朴素删边过了，请注意关键词：Pascal！邻接矩阵！dij！朴素删边！

天真的我傻乎乎地写了SPFA+邻接矩阵+删边无判重 还沾沾自喜地以为一遍AC

于是样例一遍AC了= =

于是评测十个点过了四个···

于是调试了一个小时发现判断是否在队列中的数组in忘了改为false···

于是还是挂···因为出现了奇怪的小行星\*\*\*

于是把注释都删除 再测，还是挂···

请里奥大神莅临指导，里奥竟不知所措，久之，默言曰：重装

然而鄙人还有点智商 没有重装 因为codevs也有小星星···

于是很久以后才发现在某行代码的右边 屏幕不可及之处 有一行小小的代码TUT欲哭无泪

删除，再调，再交，还是挂了

之后各种调 最终一个点TLE···

是时已至午时，烈日当空，肚子咕咕叫，没赶上吃饭···

下午来了加优化！重新把优先队列双端队列重载运算符那一套都捣鼓出来 于是···我该说什么原来T一个点优化之后T了三个点···

我意志力真是坚强···

但我不甘心啊！不甘心啊啊啊！！！

后来的后来，不知过了多久，看了黄学长的代码和一位小学生时代就拿奖的常州神犇的解释···果然邻接矩阵什么的若爆了，还得上邻接表

所以说dij+矩阵AC的小盆友你是RP太好了吗···

研究黄学长代码半天，终有所获···

上代码

思路：类似第K短路 好吧 先SPFA球一遍最短路 然后对于这条路上的每条边枚举删边 再求最短路 取最大值即可

首先是我的最终版SPFA+矩阵 无优化 一个点超时

//codevs1021 ÂêÀö¿¨ É¾±ß×î¶ÌÂ· SPFA
    //copyright by ametake
    //first time to write SPFA&&edge deleted shortest road,HURRY UP! 
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    const int maxn=1000+10;
    int v,e,map[maxn][maxn],dist[maxn],pre[maxn],head=0,tail=0,res;
    bool in[maxn];
    queue
          
            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
           
            dist[u]+map[u][i]) { if ((u!=head)||(i!=tail)) { dist[i]=dist[u]+map[u][i]; pre[i]=u; if (!in[i]) q.push(i); in[i]=true; } } } } res=dist[v]; 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; }

接下来是改进（糟蹋）后的SLF+LLL优化 用了优先队列 还用了结构体 比较函数是自写重载小于号 STL相关都重载小于号 但是李晨的高精重载了大于号 不知为什么

另外 亲测这种形式的优先队列可用 自动依照里面dist比较函数排序

//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; }

接下来是黄学长（hzwer）的正解代码 简洁明了 邻接表存储边 删除时直接删边 同时通过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

`所以这告诉我们果然还是要好好学习啊啊 试着写写香甜的黄油 另外文化课加油哦~ ——逝者如斯，而未尝往也；盈虚者如彼，而卒莫消长也。`