首页 > 代码库 > CodeForces 449B - Jzzhu and Cities
CodeForces 449B - Jzzhu and Cities
传送门：Jzzhu and Cities
题意：
题意一定要看仔细，这里说一个国家，有N个城市，城市与城市之间有M条路，距离为W，编号为1的城市是首都，1和K个城市有火车道，距离为X
现在国家要节省开支，想把其中部分铁路关闭，但是又想关闭之后从首都到每一个城市本来的最短距离不变，求最多能关闭多少条铁路。
分析：
注意最重要的几点：
1、求关闭最多的铁路
2、关闭之后，从首都到每一个城市的最短距离不变。
3、从首都到某个城市的铁路可能有多条
算法：
很明显，求最短距离不变，那么就是最短路径问题，DIJK算法用上。
从首都到某个城市，有两种方式
1、走路
2、坐火车
但是为了节省，如果走路的距离==坐火车，那么这条火车道就干掉。
那么好了，知道这点，我们就必须先求走路的距离，再求一下坐火车的距离，判断一下是否相等就可以了。
如果火车比走路更远，干掉。
但是要注意一点：
可能从首都有多条铁路到某一个城市，那么一定一定要想到，我们只需要最短那条铁道来判断，其他比他远的，留来干嘛！！！！（我这里没判重，坑了好久）。
接下来就是第二点：
从首都到某个城市的距离，我们中途是可以坐火车的！！！！那么这个距离可能跟你从首都直接坐火车到这个城市的距离相等，这条铁路也得干掉！！！！（第二个坑）
好了，现在就可以求最多多少条了。
首先，最短路径，先去掉所有铁路求一次，那么就得到从首都走路到其他城市的所有最短距离
再把铁路全部加上，那么就求到（可能）加上坐火车到其他城市的最短距离。
之后就是判断，这条铁路是否需要就可以了。
判断的依据是，在DIJK算法里面加一个pre[v] = u ，记录v是从u这个城市过来的。
转移的时候，如果u是首都1，并且存在一个u‘，跟从首都1直接坐火车到v的距离相等，那么我们就抛弃从首都坐火车这条，改为从首都到 u‘再走路过来v这条路，那么就又少一条铁路了。
之后把这些情况加上，就是最多能删多少条铁路了。
1 #ifndef ONLINE_JUDGE 2 #define __DEBUG__ 0 3 #endif 4 /* 5 * ======================================= 6 * FileName: code.cpp 7 * Desc: 8 * Author: vinceliang 9 * Email: liangguoqiu@gmail.com 10 * HomePage: 11 * Version: 0.0.1 12 * LastChange: 2014-07-15 12:16:49 13 * History: 14 *======================================== 15 */ 16 #ifdef __DEBUG__ 17 #define Log(...) printf(__VA_ARGS__) 18 #else 19 #define Log(...) // 20 #endif 21 #include <algorithm> 22 #include <string> 23 #include <complex> 24 #include <cassert> 25 #include <memory> 26 #include <set> 27 #include <stack> 28 #include <map> 29 #include <list> 30 #include <deque> 31 #include <numeric> 32 #include <cctype> 33 #include <cstddef> 34 #include <vector> 35 #include <queue> 36 #include <iostream> 37 #include <iomanip> 38 #include <iterator> 39 #include <cmath> 40 #include <cstdio> 41 #include <cstdlib> 42 #include <sstream> 43 #include <fstream> 44 #include <ctime> 45 #include <cstring> 46 #include <functional> 47 #include <bitset> 48 using namespace std; 49 #if defined(_MSC_VER) || defined(__BORLANDC__) 50 typedef unsigned __int64 uint64; 51 typedef unsigned __int64 ULL; 52 typedef signed __int64 int64; 53 typedef signed __int64 LL; 54 #else 55 typedef unsigned long long uint64; 56 typedef unsigned long long ULL; 57 typedef signed long long int64; 58 typedef signed long long LL; 59 #endif 60 typedef vector<int> VI; 61 typedef vector<string> VS; 62 typedef pair<int, int> PII; 63 typedef pair<int64, int64> PLL; 64 typedef vector<int64> VL; 65 #define pb push_back 66 #define pob pop_back 67 #define mp make_pair 68 #define fi first 69 #define se second 70 #define PII pair< int,int > 71 #define PSS pair< string,string > 72 #define PDD pair< double,double > 73 #define PLL pair< LL, LL > 74 #define FOR( i, a, b ) for ( int i=(a), _n=(b); i < _n; ++i ) 75 #define FORE( i, a, b ) for ( int i=(a), _n=(b); i <= _n; ++i ) 76 #define FORD( i, a, b ) for ( int i=(a), _n=(b); i >= _n; --i ) 77 #define REP( i, n ) FOR( i, 0, (n) ) 78 #define REPE( i, n ) FORE( i, 1, (n) ) 79 #define ALL( c ) (c).begin(), (c).end() 80 #define SORT( c ) sort( ALL( c ) ) 81 #define LEN( s ) (int)( (s).size() ) 82 #define CLS( a ) memset( (a),0,sizeof(a) ) 83 #define IOS ios::sync_with_stdio( false ) 84 const double PI = 3.1415926535897932384626433832795028841971; 85 const double EPS = 1E-9; 86 const int64 INF64 = (int64)1E18; 87 const int INF = 1 << 30; 88 const int maxn = 1000005; 89 90 91 int eh[maxn], tot; 92 LL dist[maxn]; 93 LL dist2[maxn]; 94 bool vist[maxn]; 95 int n, m, k; 96 97 98 struct Edge { 99 int u, v;100 LL cost;101 int next;102 Edge() {};103 Edge( int a, LL b ) { v = a, cost = b; }104 Edge( int a, int b, LL c, int d ) : u(a), v(b), cost(c), next(d) {}105 bool operator < ( const Edge &x ) const {106 return cost > x.cost;107 }108 };109 110 111 Edge edge[maxn];112 int pre[maxn];113 114 115 int Dijk( int s )116 {117 for ( int i = 1; i <= n; ++i ) 118 {119 vist[i] = false, dist[i] = INF64;120 pre[i] = 1;121 }122 dist[s] = 0;123 priority_queue< Edge > que;124 que.push( Edge( s, 0 ) );125 int ans = 0;126 while ( !que.empty() )127 {128 Edge tmp = que.top();129 que.pop();130 int u = tmp.v, cost = tmp.cost;131 if ( vist[u] ) continue;132 ans += cost, vist[u] = true;133 for ( int i = eh[u]; i != -1; i = edge[i].next )134 {135 int v = edge[i].v;136 if ( !vist[v] && ( dist[v] > dist[u] + edge[i].cost || (pre[v] == s && dist[v] == dist[u] + edge[i].cost) ) )137 {138 dist[v] = dist[u] + edge[i].cost;139 pre[v] = u;140 que.push( Edge( v, dist[v] ) );141 }142 }143 144 145 }146 return ans;147 }148 149 150 void addedge( int a, int b, LL c )151 {152 Edge e = Edge( a, b, c, eh[a] );153 edge[tot] = e;154 eh[a] = tot++;155 }156 157 158 void init()159 {160 tot = 0;161 memset( eh, -1, sizeof( eh ) );162 }163 164 165 int point[maxn];166 LL value[maxn];167 int pcnt;168 169 170 int Point1[maxn];171 int Point2[maxn];172 LL Value[maxn];173 LL MinVal[maxn];174 bool hascheck[maxn];175 176 177 void run()178 {179 //IOS;180 while( cin >> n >> m >> k ) 181 {182 pcnt = 1;183 init();184 for ( int i = 1; i <= m; ++i )185 {186 int u, v;187 LL w;188 cin >> u >> v >> w;189 addedge( u, v, w );190 addedge( v, u, w );191 Point1[i] = u;192 Point2[i] = v;193 Value[i] = w;194 }195 196 197 Dijk( 1 );198 199 200 for ( int i = 1; i <= n; ++i )201 {202 MinVal[i] = -1;203 hascheck[i] = 0;204 dist2[i] = dist[i];205 }206 207 208 init();209 210 211 for ( int i = 1; i <= m; ++i )212 {213 if ( Point1[0] == 89457 )214 {215 if ( Point1[i] == 1 || Point2[i] == 1 || Value[i] == 0 ) 216 {217 cout << Point1[i] << " " << Point2[i] << " " << Value[i] << endl;218 }219 }220 addedge( Point1[i], Point2[i], Value[i] );221 addedge( Point2[i], Point1[i], Value[i] );222 }223 224 225 for ( int i = 1; i <= k; ++i )226 {227 int s;228 LL x;229 cin >> s >> x;230 if ( MinVal[s] == -1 )231 MinVal[s] = x;232 else if ( MinVal[s] > x )233 MinVal[s] = x;234 235 236 //if ( n == 100000 )237 // cout << s << " " << x << endl;238 point[pcnt] = s;239 value[pcnt] = x;240 pcnt++;241 242 243 addedge( 1, s, x );244 addedge( s, 1, x );245 246 247 if ( x == 0 )248 cout << s << " " << x << endl;249 250 251 }252 253 254 Dijk( 1 );255 256 257 int cnt = 0;258 259 260 for ( int i = 1; i <= k; ++i )261 {262 int s;263 LL x;264 s = point[i];265 x = value[i];266 267 268 if ( MinVal[s] != x || hascheck[s] == 1 )269 {270 cnt++;271 continue;272 }273 274 275 if ( dist2[s] <= x )276 cnt++;277 else if ( dist[s] != x )278 cnt++;279 else if ( pre[s] != 1 )280 cnt++;281 282 283 284 285 hascheck[s] = 1;286 }287 288 289 cout << cnt << endl;290 }291 }292 293 294 int main( int argc, char **argv )295 {296 297 298 #ifndef ONLINE_JUDGE299 freopen("in.txt", "r", stdin);300 // freopen("out.txt", "w", stdout);301 #endif302 time_t st = clock();303 run();304 Log("\n=============\n");305 Log("Time: %.2lf sec\n", (clock() - st) / double(CLOCKS_PER_SEC));306 return 0;307 }
CodeForces 449B - Jzzhu and Cities
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。