学院"/>
【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
更多推荐
【SDOI 2010】 魔法猪学院
发布评论