SPFA及其容易被卡。。。使用请自重
Description

Alice和Bob现在要乘飞机旅行,他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务,设这些城市分别标记为0到n-1,一共有m种航线,每种航线连接两个城市,并且航线有一定的价格。Alice和Bob现在要从一个城市沿着航线到达另一个城市,途中可以进行转机。航空公司对他们这次旅行也推出优惠,他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少?
Input

数据的第一行有三个整数,n,m,k,分别表示城市数,航线数和免费乘坐次数。
第二行有两个整数,s,t,分别表示他们出行的起点城市编号和终点城市编号。(0<=s,t<n)
接下来有m行,每行三个整数,a,b,c,表示存在一种航线,能从城市a到达城市b,或从城市b到达城市a,价格为c。(0<=a,b<n,a与b不相等,0<=c<=1000)

Output
只有一行,包含一个整数,为最少花费。
Sample Input

5 6 1

0 4

0 1 5

1 2 5

2 3 5

3 4 5

2 3 3

0 2 100

Sample Output

8

HINT

对于30%的数据,2<=n<=50,1<=m<=300,k=0;

对于50%的数据,2<=n<=600,1<=m<=6000,0<=k<=1;

对于100%的数据,2<=n<=10000,1<=m<=50000,0<=k<=10.
题解
这个题目最开始一看,恩,好像玛丽卡,看起来比玛丽卡还简单。
不知道玛丽卡的点这儿玛丽卡题解
我最开始跑的SPFA跑出了最短路,我现在要让最短路上的最长的K条路变为0
后来我发现这样是错的,因为假设存在这样一组路

1->2 权值 = 10
2->3 权值 = 15
1->3 权值 = 30
那么按照假设我要从1->3必定是从1->2再从2->3,按照我的思路把2->3变为0,这样我从1->3变为10,但是事实上我们现在从1->3是0,恩,简单的贪心是错的

正解
恩,我们假设有K+1个平行宇宙(或者说是分层图?),然后我们第一层就是一次免费都不使用,而从K到K+1层连接一条从U到V权值为0。
然后这样就可以跑SPFA了。这个题目我们还可以不用建K+1层图,我们只用设置数组d【i】【k】代表从d【0】【0】到第K层的第i个点的最短距离,然后只用建一层图,而假想的在K层跑。

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

const int MAXN = 100005,MAXX = 50005,INF = 1e8;

int N,M,K,S,T,e = 1,ans = INF;
int head[MAXN],d[MAXN][11];
bool inq[MAXN][11];

inline int read(){
    int x = 0;char ch = getchar();
    while(ch < '0' || '9' < ch){ch = getchar();}
    while('0' <= ch&&ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return x;
}

struct node{
    int v,c,next;
}edge[MAXN];

struct abc{
    int u,h;
}P;

queue<abc>q;

inline void addedge(int u,int v,int c){
    edge[e] = (node){v,c,head[u]};head[u] = e++;
}

inline void init(){
    N = read();M = read();K = read();
    S = read();T = read();
    
    int u,v,c;
    
    for(int i = 1;i <= M;i++){
        u = read();v = read();c = read();
        addedge(u,v,c);addedge(v,u,c);
    }
}

inline void spfa(int S)
{
    for(int i = 0;i < N;i++)
        for(int k = 0;k <= K;k++)
            d[i][k] = INF;
    
    P.u = S;P.h = 0;
    q.push(P);d[P.u][P.h] = 0;inq[P.u][P.h] = true;
    
    while(!q.empty()){
        int u = q.front().u,h = q.front().h;q.pop();inq[u][h] = false;
        
        for(int i = head[u];i;i = edge[i].next){
            int v = edge[i].v,c = edge[i].c;
            if(d[v][h] > d[u][h] + c){
               d[v][h] = d[u][h] + c;
               if(!inq[v][h]){q.push(P = (abc){v,h});inq[v][h] = true;}
            }
            if(d[v][h+1] > d[u][h] && h < K){
                d[v][h+1] = d[u][h];
               if(!inq[v][h+1]){q.push(P = (abc){v,h+1});inq[v][h+1] = true;}
            }
            
        }
        
    }
    
    for(int i = 0;i <= K;i++) ans = min(ans,d[T][i]);
}

int main()
{
    init();
    
    spfa(S);
    
    printf("%d\n",ans);
    return 0;
}
Last modification:October 1st, 2018 at 08:20 am
If you think my article is useful to you, please feel free to appreciate