首页 > 代码库 > UVA 11374 Airport Express(优先队列优化dijstra + 枚举)
UVA 11374 Airport Express(优先队列优化dijstra + 枚举)
UVA Airport Express
题意:在Iokh市机场快线分为经济线和商业线。线路和速度价格都不同。你只有一张商业线车票,即最多只能坐一站商业线,其他时候只能坐经济线。找出一条去机场最快的线路。
思路:因为商业线只能坐一站,假如乘坐一条商业线(a,b),那么起点到a,b到终点都必须是最短路。所以先预处理起点和终点到其他所有点的最短路,分别记为f()和g(),两次dijstra即可。那么我们只需枚举每条商业线求出所有的f(a)+T(a,b)+g(b)然后求最小即可。
1w是TLE,改成了优先队列优化的dijstra,白书上的模板。
2w是RE,题目中说边数最多1000条,开到1010仍然re,果断开到10010。
#include <stdio.h> #include <algorithm> #include <set> #include <map> #include <vector> #include <math.h> #include <string.h> #include <queue> #define LL long long #define _LL __int64 using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 510; const int maxm = 10100; struct node { int u,v,w,next; }edge[maxm]; int cnt,head[maxm]; int n,m,k; int s,t; int dis_s[maxm],dis_t[maxm]; int pre_s[maxm],pre_t[maxm]; int ans; int path[maxm]; void init() { cnt = 0; memset(head,-1,sizeof(head)); } void add(int u, int v, int w) { edge[cnt] = ((struct node){u,v,w,head[u]}); head[u] = cnt++; } void dijstra(int u) { int dis[maxn],pre[maxn]; priority_queue <pair<int,int>,vector<pair<int,int> >, greater<pair<int,int> > > que; bool vis[maxn]; memset(vis,false,sizeof(vis)); for(int i = 1; i <= n; i++) { dis[i] = (i == u ? 0 : INF); } que.push(make_pair(dis[u],u)); pre[u] = -1; while(!que.empty()) { pair<int,int> p = que.top(); que.pop(); int v = p.second; if(vis[v]) continue; vis[v] = true; for(int i = head[v]; i != -1; i = edge[i].next) { if( dis[edge[i].v] > dis[v] + edge[i].w) { dis[edge[i].v] = dis[v] + edge[i].w; pre[edge[i].v] = v; que.push(make_pair(dis[edge[i].v],edge[i].v)); } } } if(u == s) { memcpy(dis_s,dis,sizeof(dis)); memcpy(pre_s,pre,sizeof(pre)); } if(u == t) { memcpy(dis_t,dis,sizeof(dis)); memcpy(pre_t,pre,sizeof(pre)); } } void solve() { int mid_u,mid_v,u,v,w; int flag = 0; int cnt,tmp; scanf("%d",&k); for(int i = 0; i < k; i++) { scanf("%d %d %d",&u,&v,&w); if(dis_s[u] + dis_t[v] + w < ans) { ans = dis_s[u] + dis_t[v] + w; mid_u = u; mid_v = v; flag = 1; } if(dis_s[v] + dis_t[u] + w < ans) { ans = dis_s[v] + dis_t[u] + w; mid_u = v; mid_v = u; flag = 1; } } if(flag == 0) { cnt = 0; tmp = t; path[cnt++] = tmp; while( pre_s[tmp] != -1) { path[cnt++] = pre_s[tmp]; tmp = pre_s[tmp]; } for(int i = cnt-1; i > 0; i--) printf("%d ",path[i]); printf("%d\n",path[0]); printf("Ticket Not Used\n"); } else { cnt = 0; tmp = mid_u; path[cnt++] = tmp; while(pre_s[tmp] != -1) { path[cnt++] = pre_s[tmp]; tmp = pre_s[tmp]; } for(int i = cnt-1; i >= 0; i--) printf("%d ",path[i]); cnt = 0; tmp = mid_v; path[cnt++] = tmp; while(pre_t[tmp] != -1) { path[cnt++] = pre_t[tmp]; tmp = pre_t[tmp]; } for(int i = 0; i < cnt-1; i++) printf("%d ",path[i]); printf("%d\n",path[cnt-1]); printf("%d\n",mid_u); } printf("%d\n",ans); } int main() { int item = 0; while(~scanf("%d %d %d",&n,&s,&t)) { if(item) printf("\n"); init(); int u,v,w; scanf("%d",&m); for(int i = 0; i < m; i++) { scanf("%d %d %d",&u,&v,&w); add(u,v,w); add(v,u,w); } dijstra(s); //预处理 dijstra(t); ans = dis_s[t]; solve(); item++; } return 0; }
UVA 11374 Airport Express(优先队列优化dijstra + 枚举)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。