oj.uz

답안 #412994

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
412994 2021-05-28T00:51:51 Z Chaska Robot (JOI21_ho_t4) C++11
0 / 100
 1874 ms 104896 KB 
#include <bits/stdc++.h> 
#define pb push_back
#define sp " "
#define sl "\n"
#define fi first
#define se second
#define mp make_pair
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define rev(a) reverse(a.begin(),a.end())
#define PI 3.141592
#define fo(i,n) for (int i=0;i<n;i++)
#define fofo(i,n,j,m) for (int i=0;i<n;i++) for (int j=0;j<m;j++) 
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
const int N=1e5+5,M=2e5+5,mod=1e9+7;

ll n,m;
map<ll,ll> h[N];
map<ll,ll> hp[N];
vector<ll> g[N];
map<ii,ll> pr;
map<ii,ll> co;
bool vs[N];
ll res[N];
priority_queue<ii,vector<ii>,greater<ii>> pq;
void dij(ll cost,ll node)
{
	if (vs[node]) return;
	vs[node] = true;
	res[node] = cost;
	for (int u : g[node]) {
		if (!vs[u] && h[node][co[{node,u}]]==1) {
			pq.push({cost,u});
			//dij(u,cost);
		}
	}
	for (int u : g[node]) {
		if (!vs[u]) if (h[node][co[{node,u}]]>1) {
			pq.push({cost+min(pr[{node,u}],hp[node][co[{node,u}]]),u});
			//dij(u,cost);
		}
	}
}

int main() { 
	cin.tie(0); cout.tie(0); 
	ios_base::sync_with_stdio();
	cin >> n >> m;
	for (int i=0;i<m;i++) {
		ll a,b,c,p;
		cin >> a >> b >> c >> p;
		co[{a,b}] = c;
		co[{b,a}] = c;
		pr[{a,b}] = p;
		pr[{b,a}] = p;
		g[a].push_back(b);
		g[b].push_back(a);
		h[a][c]++;
		hp[a][c] += p;
		h[b][c]++;
		hp[b][c] += p;
	}
	pq.push({0,1});
	while (!pq.empty()) {
		auto x = pq.top();
		pq.pop();
		dij(x.fi,x.se);
	}
	if (!vs[n]) cout << -1;
	else cout << res[n];
	return 0;
}

// Recuerda limites 
// Recuerda casos especiales

Subtask #1
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11980 KB Output is correct
2 Correct 8 ms 11980 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 7 ms 12044 KB Output is correct
5 Correct 7 ms 12040 KB Output is correct
6 Correct 7 ms 12048 KB Output is correct
7 Incorrect 9 ms 12316 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 474 ms 45328 KB Output is correct
2 Correct 203 ms 27452 KB Output is correct
3 Correct 902 ms 58440 KB Output is correct
4 Correct 302 ms 34012 KB Output is correct
5 Incorrect 1874 ms 104896 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11980 KB Output is correct
2 Correct 8 ms 11980 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 7 ms 12044 KB Output is correct
5 Correct 7 ms 12040 KB Output is correct
6 Correct 7 ms 12048 KB Output is correct
7 Incorrect 9 ms 12316 KB Output isn't correct
8 Halted 0 ms 0 KB -