P2939 [USACO09FEB]改造路Revamping Trails（分层图最短路）「建议收藏」

全栈程序员-站长 • 2022年4月20日下午4:00 • 未分类 • 阅读 173

大家好，又见面了，我是你们的朋友全栈君。

完了我好像连分层图最短路都不会了……果然还是太菜了……

具体来说就是记录一个步数表示免费了几条边，在dijkstra的时候以步数为第一关键字，距离为第二关键字。枚举边的时候分别枚举免不免费下一条边。然后其他基本就和普通的dijkstra一样了

据说这题卡spfa，特意把刚写好的spfa给改了（很懵逼为啥写spfa全T，我写挂了？）

 1 //minamoto
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<queue>
 5 #include<cstring>
 6 using namespace std;
 7 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
 8 char buf[1<<21],*p1=buf,*p2=buf;
 9 inline int read(){
10     #define num ch-'0'
11     char ch;bool flag=0;int res;
12     while(!isdigit(ch=getc()))
13     (ch=='-')&&(flag=true);
14     for(res=num;isdigit(ch=getc());res=res*10+num);
15     (flag)&&(res=-res);
16     #undef num
17     return res;
18 }
19 const int N=10005,M=100005,K=25;
20 struct node{
21     int x,cnt,dis;
22     node(){}
23     node(int x,int cnt,int dis):x(x),cnt(cnt),dis(dis){}
24     inline bool operator <(const node b)const
25     {
   
   return cnt!=b.cnt?cnt>b.cnt:dis>b.dis;}
26 };
27 priority_queue<node> q;
28 int vis[N][K],dis[N][K];
29 int head[N],Next[M],ver[M],edge[M],tot;
30 int n,m,k;
31 inline void add(int u,int v,int e){
32     ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e;
33     ver[++tot]=u,Next[tot]=head[v],head[v]=tot,edge[tot]=e;
34 }
35 void dijkstra(){
36     memset(dis,0x3f,sizeof(dis));
37     memset(vis,0,sizeof(vis));
38     q.push(node(1,0,0)),dis[1][0]=0;
39     while(!q.empty()){
40         int u=q.top().x,cnt=q.top().cnt;q.pop();
41         if(vis[u][cnt]) continue;
42         vis[u][cnt]=1;
43         for(int i=head[u];i;i=Next[i]){
44             int v=ver[i];
45             if(dis[v][cnt]>dis[u][cnt]+edge[i]){
46                 dis[v][cnt]=dis[u][cnt]+edge[i];
47                 q.push(node(v,cnt,dis[v][cnt]));
48             }
49             if(cnt+1<=k&&dis[v][cnt+1]>dis[u][cnt]){
50                 dis[v][cnt+1]=dis[u][cnt];
51                 q.push(node(v,cnt+1,dis[v][cnt+1]));
52             }
53         }
54     }
55 }
56 int main(){
57 //    freopen("testdata.in","r",stdin);
58     n=read(),m=read(),k=read();
59     for(int i=1,u,v,e;i<=m;++i)
60     u=read(),v=read(),e=read(),add(u,v,e);
61     dijkstra();
62     printf("%d\n",dis[n][k]);
63     return 0;
64 }