【SDOI 2010】 魔法猪学院

学院"/>

【SDOI 2010】 魔法猪学院

【题目链接】

            .php?id=1975

【算法】

           A*求k短路

【代码】

#include<bits/stdc++.h>
using namespace std;
#define MAXN 5010
#define MAXM 200010
const double INF = 1e15;int i,tot,n,m,u,v;
int head[MAXN],rhead[MAXN];
double dist[MAXN];
double w,val;struct Edge
{int to;double w;int nxt;
} e[MAXM<<1];
struct info
{int s;double d;friend bool operator < (info a,info b){return a.d + dist[a.s] > b.d + dist[b.s];}
} ;inline void add(int u,int v,double w)
{tot++;e[tot] = (Edge){v,w,head[u]};head[u] = tot;tot++;e[tot] = (Edge){u,w,rhead[v]};rhead[v] = tot;    
}
inline void dijkstra(int s)
{int i,u,v;double w;priority_queue< pair<double,int> > q;static bool vis[MAXN];memset(vis,false,sizeof(vis));while (!q.empty()) q.pop();for (i = 1; i <= n; i++) dist[i] = INF;dist[s] = 0;q.push(make_pair(0,s));while (!q.empty()){u = q.top().second;q.pop();if (vis[u]) continue;vis[u] = true;for (i = rhead[u]; i; i = e[i].nxt){v = e[i].to;w = e[i].w;if (dist[u] + w < dist[v]){dist[v] = dist[u] + w;q.push(make_pair(-dist[v],v));}}}        
}
inline int Astar(int s,int t)
{int i,cnt = 0,v;double w,sum = 0;priority_queue< info > q;info cur;while (!q.empty()) q.pop();q.push((info){s,0});while (!q.empty()){cur = q.top();q.pop();if (cur.s == t){if (sum + cur.d <= val) {sum += cur.d;cnt++;} else return cnt;}for (i = head[cur.s]; i; i = e[i].nxt){v = e[i].to;w = e[i].w;q.push((info){v,cur.d+w});}}return 0;
}int main() 
{scanf("%d%d%lf",&n,&m,&val);for (i = 1; i <= m; i++){scanf("%d%d%lf",&u,&v,&w);add(u,v,w);        }dijkstra(n);printf("%d\n",Astar(1,n));return 0;}

转载于:.html