Submission #661181

#	Time	Username	Problem	Language	Result	Execution time	Memory
661181		kinope	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	1091 ms	2836 KiB

ho_t4

#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<ll, int> pii;
typedef pair<ll, pair<int, int>> pii2;
struct st{int a, b; ll c, d;} kraw[50000];

vector<pii2> g2[201];
ll odl2[4][201]; //0. to z 1 do innych, 1. to z n do innych, 2. to z innych do 1, 3. to z innych do n

void dijkstra2(int s, int b, int BL){
		priority_queue<pii> pq;
		pq.emplace(0, s);
		odl2[b][s] = 0;
		while(!pq.empty()){
				int x = pq.top().ss; ll dis = -pq.top().ff;
				pq.pop();
				for(pii2 u : g2[x]){
						if(u.ss.ss == BL) continue;
						if(odl2[b][u.ss.ff] > dis + u.ff){
								odl2[b][u.ss.ff] = dis + u.ff;
								pq.emplace(-odl2[b][u.ss.ff], u.ss.ff);
						}
				}
		}
}

int main(){
		
		int n, m, a, b; ll c, d;
		scanf("%d%d", &n, &m);
		for(int i = 0; i <= n; ++i)
				for(int j = 0; j <= n; ++j) odl2[0][i] = odl2[1][i] = 1e18;
		
		for(int i = 0; i < m; ++i){
				scanf("%d%d%lld%lld", &a, &b, &c, &d);
				kraw[i] = {a, b, c, d};
				g2[a].push_back({c, {b, i}});
		}
		
		ll wynik = 1e18;
		
		for(int i = 0; i < m; ++i){
				a = kraw[i].a, b = kraw[i].b, c = kraw[i].c, d = kraw[i].d;
				g2[b].push_back({c+d, {a, 0}});
				dijkstra2(1, 0, i);
				dijkstra2(n, 1, i);
				g2[b].pop_back();
				wynik = min(wynik, odl2[0][n] + odl2[1][1]);
				for(int j = 1; j <= n; ++j) odl2[0][j] = odl2[1][j] = 1e18;
		}
		dijkstra2(1, 0, 0);
		dijkstra2(n, 1, 0);
		wynik = min(wynik, odl2[0][n] + odl2[1][1]);
		
		if(wynik != 1e18) printf("%lld\n", wynik);
		else printf("-1");
		
		
		return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
ho_t4.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d%d%lld%lld", &a, &b, &c, &d);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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