【bzoj2763】 [JLOI2011]飞行路线

2015.02.01 10:36 Sun | 22次阅读 | 旧日oi | 固定链接 | 源码

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.

题解

以前虽然没做过这种题但是看了一眼也大致有了个思路,a了之后问老师才知道原来这叫分层图,还是个很高深的知识,等着再去研究研究……
spfa不优化在有些oj过不了,bzoj上能从6000+ms变成208ms……

我的程序

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define maxn 10005
#define maxm 50005
using namespace std;
int n,m,k,st,ed;
struct edge{
    int to;
    int next;
    int val;
}e[maxm<<1];
int h[maxn],tp;
void ae(int u,int v,int w)
{
    e[++tp].to=v;e[tp].next=h[u];e[tp].val=w;h[u]=tp;
}
int dis[maxn][11];
bool vis[maxn][11];
struct node{
    int no;
    int times;
    friend bool operator < (node n1, node n2)
    {
        return dis[n1.no][n1.times]>dis[n2.no][n2.times];
    }
};
#include<queue>
priority_queue<node> q;
void spfa()
{
    memset(dis,0x3f,sizeof(dis));
    for(int i=0;i<=k;i++)
    vis[st][i]=1,dis[st][i]=0;
    node temp;temp.no=st;temp.times=0;
    int u,t;
    q.push(temp);
    while(!q.empty())
    {
        temp=q.top();q.pop();
        u=temp.no,t=temp.times;
        for(int v,i=h[u];i;i=e[i].next)
        {
            v=e[i].to;
            if(dis[v][t]>dis[u][t]+e[i].val){
                dis[v][t]=dis[u][t]+e[i].val;
                if(!vis[v][t])
                {
                    vis[v][t]=1;
                    temp.no=v,temp.times=t;
                    q.push(temp);
                }
            }
            if(t<k&&dis[v][t+1]>dis[u][t])
            {
                dis[v][t+1]=dis[u][t];
                if(!vis[v][t+1])
                {
                    vis[v][t+1]=1;
                    temp.no=v,temp.times=t+1;
                    q.push(temp);
                }
            }
        }
        vis[u][t]=0;
    }
}
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    n=read(),m=read(),k=read(),st=read(),ed=read();
    int u,v,w;
    for(int i=1;i<=m;i++)
    {
        u=read(),v=read(),w=read();
        ae(u,v,w);
        ae(v,u,w);
    }
    spfa();
    int minn=0x7fffffff;
    for(int i=0;i<=k;i++)
    minn=min(minn,dis[ed][i]);
    printf("%d\n",minn);
    return 0;
}```