【HDOJ】2388 Playground Hideout

摘要:
优先级队列直接AC。

优先级队列直接AC。

  1 /* 2388 */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <algorithm>
 12 #include <cstdio>
 13 #include <cmath>
 14 #include <ctime>
 15 #include <cstring>
 16 #include <climits>
 17 #include <cctype>
 18 #include <cassert>
 19 #include <functional>
 20 #include <iterator>
 21 #include <iomanip>
 22 using namespace std;
 23 //#pragma comment(linker,"/STACK:102400000,1024000")
 24 
 25 #define sti                set<int>
 26 #define stpii            set<pair<int, int> >
 27 #define mpii            map<int,int>
 28 #define vi                vector<int>
 29 #define pii                pair<int,int>
 30 #define vpii            vector<pair<int,int> >
 31 #define rep(i, a, n)     for (int i=a;i<n;++i)
 32 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 33 #define clr                clear
 34 #define pb                 push_back
 35 #define mp                 make_pair
 36 #define fir                first
 37 #define sec                second
 38 #define all(x)             (x).begin(),(x).end()
 39 #define SZ(x)             ((int)(x).size())
 40 #define lson            l, mid, rt<<1
 41 #define rson            mid+1, r, rt<<1|1
 42 
 43 typedef struct node_t {
 44     int u, w;
 45     
 46     node_t() {}
 47     node_t(int u, int w):
 48         u(u), w(w) {}
 49     
 50     friend bool operator< (const node_t& a, const node_t& b) {
 51         return a.w > b.w;
 52     }
 53     
 54 } node_t;
 55 
 56 typedef struct {
 57     int v, w, nxt;
 58 } edge_t;
 59 
 60 const int INF = 0x3f3f3f3f;
 61 const int maxv = 1e5+5;
 62 const int maxe = 2e5+5;
 63 edge_t E[maxe];
 64 int head[maxv], l;
 65 int W[maxv];
 66 int dis[maxv];
 67 bool visit[maxv];
 68 int n, m;
 69 
 70 void init() {
 71     memset(head, -1, sizeof(head));
 72     l = 0;
 73 }
 74 
 75 void addEdge(int u, int v, int wa, int wb) {
 76     E[l].v = v;
 77     E[l].w = wa;
 78     E[l].nxt = head[u];
 79     head[u] = l++;
 80     
 81     E[l].v = u;
 82     E[l].w = wb;
 83     E[l].nxt = head[v];
 84     head[v] = l++;
 85 }
 86 
 87 int bfs() {
 88     priority_queue<node_t> Q;
 89     node_t nd;
 90     int u, v, w;
 91     
 92     // memset(dis, INF, sizeof(dis));
 93     memset(visit, false, sizeof(visit));
 94     rep(i, 0, n) {
 95         Q.push(node_t(i, W[i]));
 96         dis[i] = W[i];
 97     }
 98     
 99     while (!Q.empty()) {
100         nd = Q.top();
101         Q.pop();
102         if (visit[nd.u])
103             continue;
104         visit[u=nd.u] = true;
105         for (int k=head[u]; k!=-1; k=E[k].nxt) {
106             v = E[k].v;
107             if (dis[v] > dis[u]+E[k].w) {
108                 dis[v] = dis[u] + E[k].w;
109                 Q.push(node_t(v, dis[v]));
110             }
111         }
112     }
113     
114     int ret = 0;
115     rep(i, 1, n)
116         if (dis[i] > dis[ret])
117             ret = i;
118         
119     return ret;
120 }
121 
122 void solve() {
123     int ans = bfs();
124     
125     printf("%d

", ans);
126 }
127 
128 int main() {
129     ios::sync_with_stdio(false);
130     #ifndef ONLINE_JUDGE
131         freopen("data.in", "r", stdin);
132         freopen("data.out", "w", stdout);
133     #endif
134     
135     int t;
136     int u, v, wa, wb;
137     
138     scanf("%d", &t);
139     rep(tt, 1, t+1) {
140         scanf("%d %d", &n, &m);
141         init();
142         rep(i, 0, n)
143             scanf("%d", &W[i]);
144         rep(i, 0, m) {
145             scanf("%d %d %d %d", &u, &v, &wa, &wb);
146             addEdge(u, v, wa, wb);
147         }
148         printf("Scenario #%d:
", tt);
149         solve();
150     }
151     
152     #ifndef ONLINE_JUDGE
153         printf("time = %d.
", (int)clock());
154     #endif
155     
156     return 0;
157 }

免责声明:文章转载自《【HDOJ】2388 Playground Hideout》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇【POJ】1743 Musical Theme【HDOJ】4261 Estimation下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

基于色彩恒常( color constancy)特性的FrankleMcCann Retinex图像增强。

由于CSDN博客和博客园的编辑方面有不一致的地方,导致文中部分图片错位,为不影响浏览效果,建议点击打开链接。 相关随笔可见:带色彩恢复的多尺度视网膜增强算法(MSRCR)的原理、实现及应用。 从历史的顺序上讲,本篇应该放在MSRCR之前的,只是由于现在大多论文都是描述的MSRCR,因此我也是先学习MSRCR的。 今天,无意中找寻一些Retinex资料,搜索到...

新氧 ubuntu 中文定制版

“新氧ubuntu中文定制版”是由新氧ubuntu中文定制版项目组在近期推出的一个基于Ubuntu的中文Linux发行版。 根据其描述:新氧 ubuntu 中文定制版,是基于 ubuntu 官方发布版制作的中文优化应用版本。它不是一个新的发布版。 新氧ubuntu中文定制版是一个非盈利项目,因为其包含了一些独特的适用于中文用户的组件,一经推出就受到了广泛的...

C++ Sockets Library

C++ Sockets Library C++ Socket Library programming example Example: a small httpget program Usage:$ httpget http://www.alhem.net/Sockets/index.html View source code: httpget.cppa...

输出所有在给定范围内的水仙花数

内容:输出所有在给定范围内的水仙花数 目的:掌握循环与if语句 程序代码: /* * 程序的版权和版本声明部分: * Copyright (c) 2013, 烟台大学计算机学院 * All rights reserved. * 文件名称:test.cpp * 作 者:匡效国 * 完成日期:2013 年 4 月 10 日 *...

Web编程所需的必要知识、环境工具相关

在《伴您一起成长》论坛中也发过帖: http://17chengzhang.zzxx.in/viewthread.php?tid=109&extra=page%3D1&frombbs=1 ”工欲善其事,必先利其器“。 初学者如何起步做网页(网站)? 以下,罗列出一些知识及工具,从这里开始吧!...

install PostgreSQL Community Ubuntu Documentation

PostgreSQL - Community Ubuntu Documentation PostgreSQL 目录 Introduction Client Installation Installation Dapper Hardy Karmic, Lucid, Intrepid and Maverick Admini...