The Shortest Path in Nya Graph [kuangbin带你飞]刷题记录

- The Shortest Path in Nya Graph

核心思想,将每一层建立俩个辅助点,如图,让该层的所有点与这两个点相连,边权分别为c与0,就成功地把建边的时间复杂度大大缩小了,如图

AC代码

#include<iostream>
#include<queue>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstdio>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
#define repi(x,y,z) for(int x = y; x<=z;++x)
#define deci(x,y,z) for(int x = y; x>=z;--x)
#define repl(x,y,z) for(ll x = y; x<=z;++x)
#define decl(x,y,z) for(ll x = y; x>=z;--x)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b / gcd(a, b))
#define INF 0x3f3f3f3f
#define CAS int cas;cin>>cas;while(cas--)
#define py  puts("Yes")
#define pn  puts("No")
#define pcn  putchar('\n')
inline int read( ) {int f = 1,x = 0;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();}x *= f;return x;
}
const int maxn=1e5+5;int cnt=0;
struct cpp {int to,next;ll cost;
}edge[ 800005 ],tem;
int head[ 300105 ];
void inta(){cnt=0;memset( head,-1,sizeof(head) );
}
void addEdge(int from,int to,ll cost){cnt++;edge[cnt].to = to;edge[cnt].cost = cost;edge[cnt].next = head[from];head[from] =cnt;
}bool vis[300105];
ll dis[300105];bool operator<(const cpp&a,const cpp&b){return a.cost>b.cost;
}
int n,m;
ll c;
void Dijkstra(int s){repi(i,0,n*3+5) dis[i]=1e15,vis[i]=0;priority_queue<cpp> dui;dis[s]=0;tem.cost=0;tem.to=s;dui.push(tem);int u;while(!dui.empty()){u=dui.top().to;dui.pop();if(vis[u]) continue;vis[u]=1;for(int i=head[u];i!=-1;i=edge[i].next){if( vis[edge[i].to]==0 && dis[edge[i].to]>dis[u]+edge[i].cost ){dis[edge[i].to]=dis[u]+edge[i].cost;tem.to=edge[i].to;tem.cost=dis[edge[i].to];dui.push(tem);}}}
}int aa,bb;
ll cc;void solve(int &t){inta();n=read();m=read();c=(ll)read();int tema;repi(i,1,n){tema=read();addEdge(n+tema*2+1,i,0);addEdge(i,n+tema*2,0);}repi(i,1,n-1){addEdge(n+i*2,n+i*2+3,c);addEdge(n+i*2+2,n+i*2+1,c);}while(m--){aa=read();bb=read();cc=(ll)read();addEdge(aa,bb,cc);addEdge(bb,aa,cc);}Dijkstra(1);if( dis[n]==1e15 )dis[n]=-1;printf("Case #");printf("%d",t);printf(": ");
//    printf("%d\n",d[n]);cout<<dis[n]<<endl;
}int main(){int t;t=read();repi(i,1,t){solve(i);}
}