제출 #212543

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
212543		b00n0rp	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	989 ms	2940 KiB

ho_t4

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <ratio>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

typedef long long ll;
#define int unsigned
#define pb push_back
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define remin(a,b) a = min(a,b)
typedef map<int,int> mii;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
#define F first
#define S second
#define sfl2(x,y) scanf("%lld%lld",&x,&y);
#define sfi2(x,y) scanf("%d%d",&x,&y);
#define pfi(x) printf("%d\n",x);
#define pfl(x) printf("%lld\n",x);

const int INF=1500000000;

#define runtime() ((double)clock() / CLOCKS_PER_SEC)

void solvethetestcase();
 
signed main(){

	int t = 1;
	// (UNCOMMENT FOR MULTIPLE TEST CASES) \
	sfl(t);
	FOR(testcase,1,t+1){
		// (UNCOMMENT FOR CODEJAM) \
		printf("Case #%lld: ",testcase); 
		solvethetestcase();
	}
}   
 
int n,m;
vector<pair<pii,pii> > edges;
vi adj[205];
int dist[205][205];
int p1[205],p2[205];
int lol[205];

set<int> s;

int dijkstra(){
	REP(i,205) lol[i] = INF;
	lol[1] = 0;
	priority_queue<pii,vpii,greater<pii> > pq;
	pq.push({0,1});
	while(pq.size()){
		int u = pq.top().S;
		pq.pop();
		REP(i,adj[u].size()){
			int e = adj[u][i];
			int v = edges[e].F.S,w = edges[e].S.F;
			if(lol[v] > lol[u]+w){
				lol[v] = lol[u]+w;
				pq.push({lol[v],v});
				p1[v] = e;
			}
		}
	}
	int res = lol[n];
	// if(res >= INF) return INF;
	REP(i,205) lol[i] = INF;
	lol[n] = 0;
	pq.push({0,n});
	while(pq.size()){
		int u = pq.top().S;
		pq.pop();
		REP(i,adj[u].size()){
			int e = adj[u][i];
			int v = edges[e].F.S,w = edges[e].S.F;
			if(lol[v] > lol[u]+w){
				lol[v] = lol[u]+w;
				pq.push({lol[v],v});
				p2[v] = e;
			}
		}
	}
	return res+lol[1];
}
 
void solvethetestcase(){
	sfi2(n,m)
	REP(i,205){
		p1[i] = -1;
		p2[i] = -1;
		REP(j,205){
			dist[i][j] = INF;
		}
		dist[i][i] = 0;
	}
	REP(i,m){
		int u,v,c,d;
		sfi2(u,v)
		sfi2(c,d)
		edges.pb({{u,v},{c,d}});
		adj[u].pb(i);
		// adj[v].pb(i);
		remin(dist[u][v],c);
	}
	
	FOR(k,1,n+1){
		FOR(i,1,n+1){
			FOR(j,1,n+1){
				remin(dist[i][j],dist[i][k]+dist[k][j]); 
			}
		}
	}
	int ans = dist[1][n]+dist[n][1];
	dijkstra();
	// trace(dijkstra(),ans);
	FOR(i,1,n+1){
		// trace(i,p1[i],p2[i]);
		if(p1[i] != -1) s.insert(p1[i]);
		if(p2[i] != -1) s.insert(p2[i]);
	}
	REP(i,m){
		int g = edges[i].S.S+min(dist[1][n],dist[1][edges[i].F.S]+dist[edges[i].F.F][n]+edges[i].S.F)+min(dist[n][1],dist[n][edges[i].F.S]+dist[edges[i].F.F][1]+edges[i].S.F);
		// if(g >= INF) continue;
		if(s.find(i) == s.end()){
			// trace(i,edges[i].S.S,dist[1][edges[i].F.S],dist[edges[i].F.F][n],edges[i].S.F);
			remin(ans,g);
		}
		else{
			int u,v;
			swap(edges[i].F.F,edges[i].F.S);
			u = edges[i].F.F,v = edges[i].F.S;
			adj[u].pb(i);
			REP(j,adj[v].size()){
				if(adj[v][j] == i){
					adj[v].erase(adj[v].begin()+j);
				}
			}
			// trace(i,dijkstra(),edges[i].S.S);
			remin(ans,dijkstra()+edges[i].S.S);
			swap(edges[i].F.F,edges[i].F.S);
			u = edges[i].F.F,v = edges[i].F.S;
			adj[u].pb(i);
			REP(j,adj[v].size()){
				if(adj[v][j] == i){
					adj[v].erase(adj[v].begin()+j);
				}
			}		
		}
		if(runtime() > 0.98){
			break;
		}
	}
	if(ans >= INF) pfi(-1)
	else pfi(ans)
	// cout << fixed << setprecision(10) << runtime() << endl; 
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t4.cpp:59:2: warning: multi-line comment [-Wcomment]
  // (UNCOMMENT FOR MULTIPLE TEST CASES) \
  ^
ho_t4.cpp:62:3: warning: multi-line comment [-Wcomment]
   // (UNCOMMENT FOR CODEJAM) \
   ^
ho_t4.cpp: In function 'void solvethetestcase()':
ho_t4.cpp:148:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(p1[i] != -1) s.insert(p1[i]);
      ~~~~~~^~~~~
ho_t4.cpp:149:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(p2[i] != -1) s.insert(p2[i]);
      ~~~~~~^~~~~
ho_t4.cpp:46:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sfi2(x,y) scanf("%d%d",&x,&y);
                   ~~~~~^~~~~~~~~~~~~~
ho_t4.cpp:117:2: note: in expansion of macro 'sfi2'
  sfi2(n,m)
  ^~~~
ho_t4.cpp:46:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sfi2(x,y) scanf("%d%d",&x,&y);
                   ~~~~~^~~~~~~~~~~~~~
ho_t4.cpp:128:3: note: in expansion of macro 'sfi2'
   sfi2(u,v)
   ^~~~
ho_t4.cpp:46:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sfi2(x,y) scanf("%d%d",&x,&y);
                   ~~~~~^~~~~~~~~~~~~~
ho_t4.cpp:129:3: note: in expansion of macro 'sfi2'
   sfi2(c,d)
   ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63