oj.uz

답안 #937328

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
937328 2024-03-03T21:10:33 Z amirhoseinfar1385 Robot (JOI21_ho_t4) C++17
24 / 100
 1071 ms 78540 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,maxm=200000+10;
struct yal{
	int u,v,c,w;
	int getad(int fu){
		return (u^v^fu);
	}
}alle[maxm];
int n,m,vis[maxn];
long long mainres=-1;
vector<int>adj[maxn];
map<int,int>sum[maxn];
map<int,vector<int>>all[maxn];
void vorod(){
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>alle[i].u>>alle[i].v>>alle[i].c>>alle[i].w;
		adj[alle[i].u].push_back(i);
		adj[alle[i].v].push_back(i);
		sum[alle[i].u][alle[i].c]+=alle[i].w;
		sum[alle[i].v][alle[i].c]+=alle[i].w;
		all[alle[i].u][alle[i].c].push_back(i);
		all[alle[i].v][alle[i].c].push_back(i);
	}
}
set<pair<int,pair<int,int>>>st;

void aval(int u,int w){
	for(auto x:adj[u]){
		int v=alle[x].getad(u);
		st.insert(make_pair(w+min(alle[x].w,sum[u][alle[x].c]-alle[x].w),make_pair(v,-1)));
		st.insert(make_pair(w,make_pair(v,x)));
	}
}

void upd(int u,int ind,int w){
	if(ind==-1){
		return ;
	}
	int f=0;
	for(auto x:all[u][alle[ind].c]){
		if(x==ind){
			f=1;
			continue;
		}
		int v=alle[x].getad(u);
		st.insert(make_pair(w+sum[u][alle[x].c]-alle[x].w,make_pair(v,-1)));
	}
	all[u][alle[ind].c].clear();
	if(f){
		all[u][alle[ind].c].push_back(ind);
	}
}

void solve(){
	aval(1,0);
	vis[1]=1;
	while((int)st.size()>0){
		auto x=*st.begin();
		st.erase(x);
		int u=x.second.first,w=x.first,from=x.second.second;
		if(x.second.first==n&&from==-1){
			mainres=x.first;
			return ;
		}
		if(vis[u]==0&&from==-1){
			aval(u,w);
			vis[u]=1;
		}
		upd(u,from,w);
	}
}

void khor(){
	cout<<mainres<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	freopen("inp.txt","r",stdin);
	vorod();
	solve();
	khor();
}

Subtask #1
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 2 ms 12888 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Incorrect 3 ms 12892 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 218 ms 34176 KB Output is correct
2 Correct 76 ms 23900 KB Output is correct
3 Correct 167 ms 33616 KB Output is correct
4 Correct 105 ms 27612 KB Output is correct
5 Correct 1071 ms 78540 KB Output is correct
6 Correct 894 ms 67844 KB Output is correct
7 Correct 504 ms 68760 KB Output is correct
8 Correct 417 ms 40708 KB Output is correct
9 Correct 440 ms 40788 KB Output is correct
10 Correct 335 ms 44884 KB Output is correct
11 Correct 95 ms 31060 KB Output is correct

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 2 ms 12888 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Incorrect 3 ms 12892 KB Output isn't correct
7 Halted 0 ms 0 KB -