201712-4 行车路线(最短路 spfa)

我会带着你远行 2022-05-18 08:12 108阅读 0赞

题目链接  
[行车路线][Link 1]

题目大意:给定路的长度，以及路的类型，分大路和小路，走大路的开销就是路的长度，走小路的开销是其长度（如果连续走小路，这里的长度是连续小路长度的和）的平方。求从起点1到n的最小开销

解题思路：  
这题的巧妙之处就在于把大小路分开存在两张图中，然后分别求最短路。如果某一个节点u，走大路和走小路的最少开销一样，那么走大路，因为走小路对之后继续走小路产生影响。

为了方便计算，我们可以先用floyd先对小路进行一个初始化，求出任意两点间最短路  
然后用spfa对大小路求最短路，最后答案就是min(dist\[n\],dist2\[n\])

AC代码

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <cstring>
    
    using namespace std;
    
    const int MAXN=520;
    const long long INF=4557430888798830399LL; 这个值貌似是long long的一个特殊值emmmm
    
    int n,m;
    long long G[MAXN][MAXN],G2[MAXN][MAXN];
    long long dist[MAXN],dist2[MAXN];
    int vis[MAXN];
    
    void floyd(){
        for(int i=1; i<=n; ++i){
            for(int j=i+1; j<=n; ++j){
                for(int k=1; k<=n; ++k){
                    G2[i][j]=min(G2[i][j],G2[i][k]+G2[k][j]);
                }
            }
        }
    }
    
    void spfa(int st){
        queue<int> q;
        dist[st]=dist2[st]=0;
        vis[st]=1;
        q.push(st);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            vis[u]=0;
            for(int i=1; i<=n; ++i){
                int mlen=min(dist[u],dist2[u]);
                int flag=0;
                if(dist[i] > mlen + G[u][i])
                {
                    dist[i] = mlen + G[u][i];
                    flag = 1;
                }
                if(G2[u][i]!=INF)
                {
                    if(dist2[i] > dist[u] + G2[u][i] * G2[u][i])
                    {
                        dist2[i] = dist[u] + G2[u][i] * G2[u][i];
                        flag = 1;
                    }
                }
                if(flag&&!vis[i]){
                    vis[i]=1;
                    q.push(i);
                }
            }
        }
    }
    void init(){
        for(int i=0; i<MAXN; ++i)
            for(int j=0; j<MAXN; ++j)
                G[i][j]=G2[i][j]=INF;
        for(int i=0; i<MAXN; ++i)
            dist[i]=dist2[i]=INF;
    
        memset(vis,0,sizeof(vis));
    }
    
    int main(){
        scanf("%d%d",&n,&m);
        long long t,a,b,c;
        init();
        for(int i=0; i<m; ++i){
            scanf("%lld%lld%lld%lld",&t,&a,&b,&c);
            if(t) G2[a][b]=G2[b][a] = min(G2[a][b],c);
            else G[a][b]=G[b][a] = min(G[a][b],c);
        } 
        floyd();
        spfa(1);
        printf("%lld",min(dist[n],dist2[n]));
        return 0;
    }

[Link 1]: http://118.190.20.162/view.page?gpid=T65