题解 P2384 【最短路】

这个题显而易见是用SPFA做的,

没错!我一眼看过去就像是差分约束

有点不友好了哈!QWQ

当AC后看题解忽然只想吐槽,表示这个方法太麻烦了,还要log()啥的……

其实主要不是嫌麻烦,是我实在不会用函数……

首先是存图(加边):

void add(int x , int y , int z) {
    a[t].x = x ;
    a[t].y = y ;
    a[t].z = z ;
    a[t].next = head[x] ;
    head[x] = t ++ ;
}

然后就是spfa

就是因为这道题求的是乘法,所以有一点小小的改动。

void spfa(int s)//SPFA板子 
{
    queue<int>q ;
    for(int i = 1 ; i <= n ; i ++) dis[i] = inf ;
    memset(vis , false , sizeof(vis)) ;
    q.push(s) ;
    dis[s] = 1 ;//这个地方注意一下!! 
    while(!q.empty())
    {
        int u = q.front() ;
        q.pop() ;
        vis[u] = false ;
        for(int i = head[u] ; i != -1 ; i = a[i].next)
        {
            int v = a[i].y;
            if(dis[v] > dis[u] * a[i].z) //注意用乘法! 
            {
                dis[v] = dis[u] * a[i].z ;
                if(!vis[v])
                {
                    vis[v] = true ;
                    q.push(v) ;
                }
            }
        }
    }
}

 

不说一些,上代码。

较难理解的地方应该都有注释.

哦,我的spfa写法和别人不太一样。

#include<iostream>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>

const int maxn = 300001 ;
const int inf = 2147483647 ;

struct dy{
    int x , y , z , next ;我的写法好像有些多余
}a[1000001];

using namespace std ;

int head[maxn] , vis[maxn] , dis[maxn] ;
int n , m , t ;

void add(int x , int y , int z) {//加边
    a[t].x = x ;
    a[t].y = y ;
    a[t].z = z ;
    a[t].next = head[x] ;
    head[x] = t ++ ;
}

void spfa(int s)//SPFA板子 
{
    queue<int>q ;
    for(int i = 1 ; i <= n ; i ++) dis[i] = inf ;
    memset(vis , false , sizeof(vis)) ;
    q.push(s) ;
    dis[s] = 1 ;//这个地方注意一下!! 
    while(!q.empty())
    {
        int u = q.front() ;
        q.pop() ;
        vis[u] = false ;
        for(int i = head[u] ; i != -1 ; i = a[i].next)
        {
            int v = a[i].y;
            if(dis[v] > dis[u] * a[i].z) //注意用乘法! 
            {
                dis[v] = dis[u] * a[i].z ;
                if(!vis[v])
                {
                    vis[v] = true ;
                    q.push(v) ;
                }
            }
        }
    }
}

int main()
{
    int a , b , c , s , e ;
    cin >> n >> m ;
    s= 1 ;//个人小习惯,很诡异…… 
    e = n ;
    t = 0 ;
    memset(head , -1 , sizeof(head)) ;
    while( m -- )//输入 
    {
        cin >> a >> b >> c ;
        add(a,b , c) ;
     } 
     spfa(s) ;
     cout << dis[n] ;
 } 

ps:今日恭喜“星辰”加入洛谷大家庭!!(呱唧呱唧……) 

完结散花!!