https://nanti.jisuanke.com/t/31445

題意

能否在t時間內把第k短路走完。

分析

A*算法板子。

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <algorithm> #include <cmath> #include <ctime> #include <vector> #include <queue> #include <map> #include <stack> #include <set> #include <bitset> using namespace std; typedef long long ll; typedef unsigned long long ull; #define ms(a, b) memset(a, b, sizeof(a)) #define pb push_back #define mp make_pair #define pii pair<int, int> #define eps 0.0000000001 #define IOS ios::sync_with_stdio(0);cin.tie(0); #define random(a, b) rand()*rand()%(b-a+1)+a #define pi acos(-1) //const ll INF = 0x3f3f3f3f3f3f3f3fll; const int inf = 1e9; const int maxn = 1000 + 10; const int maxm = 100000 + 10; const int mod = 1000000007; int head[maxn],nxt[maxm],head1[maxn],nxt1[maxm]; int dis[maxn]; bool vis[maxn]; int n,m,e,st,en,k,t; struct note{int u,v,c;note(){}note(int u,int v,int c):u(u),v(v),c(c){} }p[maxm]; struct POJ{int v,c;POJ(){}POJ(int v,int c):v(v),c(c){}bool operator < (const POJ& other)const{return c+dis[v]>other.c+dis[other.v];} }; void addnote(int u,int v,int c){p[e]=note(u,v,c);nxt[e]=head[u];head[u]=e;nxt1[e]=head1[v];head1[v]=e++; } void dij(int src){memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++) dis[i]=inf;dis[src]=0;priority_queue<POJ> que;que.push(POJ(src,0));while(!que.empty()){POJ pre=que.top();que.pop();vis[pre.v]=true;for(int i=head1[pre.v];i+1;i=nxt1[i]){if(dis[p[i].u]>dis[pre.v]+p[i].c){dis[p[i].u]=dis[pre.v]+p[i].c;que.push(POJ(p[i].u,0));}}while(!que.empty()&&vis[que.top().v]) que.pop();} } int a_star(int src){priority_queue<POJ> que;que.push(POJ(src,0));k--;while(!que.empty()){POJ pre=que.top();que.pop();if(pre.v==en){if(k) k--;else return pre.c;}for(int i=head[pre.v];i+1;i=nxt[i])if(pre.c+p[i].c<=t)que.push(POJ(p[i].v,pre.c+p[i].c));}return -1; } int main(){ #ifdef LOCALfreopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); #endifwhile(~scanf("%d%d",&n,&m)){scanf("%d%d%d%d",&st,&en,&k,&t);memset(head,-1,sizeof(head));memset(head1,-1,sizeof(head1));e=0;for(int i=0;i<m;i++){int u,v,c;scanf("%d%d%d",&u,&v,&c);addnote(u,v,c);}dij(en);if(dis[st]==inf){puts("Whitesnake!");continue;} // if(st==en) k++;int ans=a_star(st);if(ans==-1||ans>t){puts("Whitesnake!");}else{puts("yareyaredawa");} // printf("%d\n",a_star(st)); }return 0; }

?

轉載于:https://www.cnblogs.com/fht-litost/p/9671523.html

總結

以上是生活随笔為你收集整理的ACM-ICPC 2018 沈阳赛区网络预赛 D Made In Heaven（第k短路，A*算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。