洛谷 P4568 [JLOI2011]飞行路线题解

每日一题 day41 打卡

Analysis

分层图最短路模板

各层内部正常连边，各层之间从上到下连权值为0的边。每向下跑一层，就相当于免费搭一次飞机。跑一遍从

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 #define maxn 4200000+10
 7 #define INF 9187201950435737471
 8 #define rep(i,s,e) for(register int i=s;i<=e;++i)
 9 #define dwn(i,s,e) for(register int i=s;i>=e;--i) 
10 using namespace std;
11 inline int read()
12 {
13     int x=0;
14     bool f=1;
15     char c=getchar();
16     for(; !isdigit(c); c=getchar()) if(c=='-') f=0;
17     for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0';
18     if(f) return x;
19     return 0-x;
20 }
21 inline void write(int x)
22 {
23     if(x<0){putchar('-');x=-x;}
24     if(x>9)write(x/10);
25     putchar(x%10+'0');
26 }
27 int n,m,k,cnt,ans,s,t;
28 int head[maxn],book[maxn],dis[maxn];
29 struct node
30 {
31     int v,w,nex;
32 }edge[maxn];
33 bool cmp(int x,int y)
34 {
35     return x>y;
36 }
37 inline void add(int x,int y,int z)
38 {
39     edge[++cnt].v=y;
40     edge[cnt].w=z;
41     edge[cnt].nex=head[x];
42     head[x]=cnt;
43 }
44 void dijkstra(int s)
45 {
46     priority_queue<pair<int,int> > q;
47     memset(book,0,sizeof(book));
48     memset(dis,127,sizeof(dis));
49     dis[s]=0;
50     q.push(make_pair(0,s));
51     while(!q.empty())
52     {
53         int from=q.top().second;
54         q.pop();
55         if(book[from]==1) continue;
56         book[from]=0;
57         for(int i=head[from];i;i=edge[i].nex)
58         {
59             int to=edge[i].v,val=edge[i].w;
60             if(dis[to]>dis[from]+val) 
61             {
62                 dis[to]=dis[from]+val;
63                 q.push(make_pair(-dis[to],to));
64             }
65         }
66     }
67 }
68 signed main()
69 {
70     n=read();m=read();k=read();
71     s=read();t=read();
72     rep(i,1,m)
73     {
74         int x=read(),y=read(),z=read();
75         add(x,y,z);
76         add(y,x,z);
77         rep(j,1,k)
78         {
79             add(j*n+x,j*n+y,z);
80             add(j*n+y,j*n+x,z);
81             add((j-1)*n+x,j*n+y,0);
82             add((j-1)*n+y,j*n+x,0);
83         }
84     }
85     dijkstra(s);
86     int temp=t;
87     int ans=dis[temp];
88     rep(i,1,k) ans=min(ans,dis[i*n+temp]);
89     write(ans);
90     return 0;
91 }

请各位大佬斧正~~（反正我不认识斧正是什么意思）~~

洛谷 P4568 [JLOI2011]飞行路线 题解

Analysis

洛谷 P4568 [JLOI2011]飞行路线题解