[链接] 我是链接, 点我呀:)
[题意]
在这里输入题意
[题解]
点可以重复走的 k 短路.
[代码]
- #include <bits/stdc++.h>
- #define LL long long
- #define rep1(i,a,b) for (int i = a;i <= b;i++)
- #define rep2(i,a,b) for (int i = a;i>= b;i--)
- #define all(x) x.begin(),x.end()
- #define pb push_back
- #define lson l,mid,rt<<1
- #define ri(x) scanf("%d",&x)
- #define rl(x) scanf("%lld",&x)
- #define rs(x) scanf("%s",x)
- #define rson mid+1,r,rt<<1|1
- const double pi = acos(-1);
- const int dx[4] = {0,0,1,-1};
- const int dy[4] = {1,-1,0,0};
- using namespace std;
- #define CL(a,num) memset(a,num,sizeof(a));
- #define inf 9999999
- #define eps 1e-6
- const int N = 1050;
- struct node
- {
- int u;
- int w;
- node (int uu,int ww):u(uu),w(ww){}
- };
- vector<node>g[N],rg[N];
- int dis[N],vis[N],tol[N];
- struct cnode
- {
- int u;
- int len;
- cnode (int uu,int ww):u(uu),len(ww){}
- friend bool operator <(cnode a,cnode b)
- {
- return a.len+dis[a.u]>b.len+dis[b.u];
- }
- };
- int n,m,s,t,k;
- int T;
- int A_star(int s)
- {
- if(dis[s]==inf)return -1;
- priority_queue<cnode>que;
- CL(tol,0);
- que.push(cnode(s,0));
- while(!que.empty())
- {
- cnode a=que.top();que.pop();
- int u=a.u;
- int len=a.len;
- tol[u]++;
- if(tol[t]==k)return len;
- rep1(i,0,(int)g[u].size()-1){
- node b=g[u][i];
- int v=b.u;
- que.push(cnode(v,len+b.w));
- }
- }
- return -1;
- }
- void spfa(int s)
- {
- int i;
- for(i=0;i<=n;i++)
- {
- dis[i]=inf;
- vis[i]=0;
- }
- dis[s]=0;
- queue<int>que;
- que.push(s);
- while(!que.empty())
- {
- int u=que.front();que.pop();
- vis[u]=0;
- //if (dis[u]>T) continue;
- rep1(i,0,(int)rg[u].size()-1){
- node b=rg[u][i];
- int v=b.u;
- if(dis[v]>dis[u]+b.w)
- {
- dis[v]=dis[u]+b.w;
- if(!vis[v])
- {
- vis[v]=1;
- que.push(v);
- }
- }
- }
- }
- }
- int main()
- {
- while(~scanf("%d%d",&n,&m))
- {
- int x,y,z;
- rep1(i,0,n){
- g[i].clear();rg[i].clear();
- }
- ri(s);ri(t);ri(k);ri(T);
- rep1(i,0,m-1){
- ri(x);ri(y);ri(z);
- g[x].push_back(node(y,z));rg[y].push_back(node(x,z));
- }
- spfa(t);
- int ans=A_star(s);
- if (ans==-1 || ans>T){
- puts("Whitesnake!");
- }else{
- puts("yareyaredawa");
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2763224.html