P4568 [JLOI2011]飞行路线分层图

题目描述

Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在

Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多

输入格式

数据的第一行有三个整数，

输出格式

只有一行，包含一个整数，为最少花费。

输入输出样例

输入 #1

输出 #1

数据范围

解题技巧

这题一看第一眼就是分层图，感觉就是很简单，然后就发现自己死了，发现K这个东西一直不好处理，然后就想，可以建K层，每一层都是完全图，然后第Z层就表示是滴Z次免费的情况，把当前点的所有出边都往下面连一个费用是0的单向边，由于在坐飞机时可以是双向边，所以当前点的指向点就要从上一层连向下一层的当前点，写成代码就是这样

 1 　　for(int i=1;i<=m;i++)
 2     {
 3         scanf("%d%d%d",&x,&y,&w);
 4         add(x,y,w);
 5         add(y,x,w);
 6         for(int j=1;j<=k;j++)
 7         {
 8             add(x+(j*n),y+(j*n),w);
 9             add(y+(j*n),x+(j*n),w);
10             add(x+((j-1)*n),y+(j*n),0);
11             add(y+((j-1)*n),x+(j*n),0);
12         }
13     }

但要注意一点，假如在第二层就可以跑到终点，但最后我们输出的答案是第K层的终点的DIS，所以每一层的终点都要往下一层的终点连一条费用为0的边，不然会出事

1  　　for(int i=1;i<=k;i++)
2     {
3         add(t+(i-1)*n,t+i*n,0);
4     }

，最后就跑一下dijkstra就行了，感觉还是最好不要用SPFA，被NOI搞的总感觉会挂掉，虽然不止一个大佬和老师说过NOIP的题目数据水。。。

最后放一下完整的代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 const int maxn=1e6+10;
 7 int n,m,k,s,t;
 8 int x,y,w;
 9 struct edge
10 {
11     int to;
12     int value;
13     int next;
14 }way[maxn*6];
15 int tot;
16 int dis[maxn];
17 bool vis[maxn];
18 int head[maxn];
19 void add(int x,int y,int w)
20 {
21     way[++tot].next=head[x];
22     way[tot].to=y;
23     way[tot].value=w;
24     head[x]=tot;
25 }
26 struct node
27 {
28     int dist,id;
29     node(){}
30     node(int dist,int id):dist(dist),id(id){}
31 };
32 bool operator <(node xi,node yi)
33 {
34     return xi.dist>yi.dist;
35 }
36 int dijkstra(int s)
37 {
38     priority_queue< node >q;
39     memset(dis,0x3f,sizeof(dis));
40     memset(vis,0,sizeof(vis));
41     q.push(node(0,s));
42     dis[s]=0;
43     while(!q.empty())
44     {
45         node t(q.top());
46         q.pop();
47         int x=t.id;
48         if(vis[x])
49         {
50             continue;
51         }
52         vis[x]=1;
53         for(int i=head[x];i;i=way[i].next)
54         {
55             int to=way[i].to;
56             if(dis[to]>way[i].value+t.dist)
57             {
58                 dis[to]=way[i].value+t.dist;
59                 q.push(node(dis[to],to));
60             }
61         }
62     }
63 }
64 int main()
65 {
66     memset(head,0,sizeof(head));
67     scanf("%d%d%d",&n,&m,&k);
68     scanf("%d%d",&s,&t);
69     for(int i=1;i<=m;i++)
70     {
71         scanf("%d%d%d",&x,&y,&w);
72         add(x,y,w);
73         add(y,x,w);
74         for(int j=1;j<=k;j++)
75         {
76             add(x+(j*n),y+(j*n),w);
77             add(y+(j*n),x+(j*n),w);
78             add(x+((j-1)*n),y+(j*n),0);
79             add(y+((j-1)*n),x+(j*n),0);
80         }
81     }
82     for(int i=1;i<=k;i++)
83     {
84         add(t+(i-1)*n,t+i*n,0);
85     }
86     dijkstra(s);
87     printf("%d",dis[t+k*n]);
88  }