Submission #1093011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093011		PieArmy	Robot (JOI21_ho_t4)	C++17	100 / 100	730 ms	83792 KiB

Main

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}

int n,m;
map<int,vector<pair<int,ll>>>komsu[100001];
bool vis[100001];
map<int,ll>mp[100001];
map<int,bool>dp[100001];

void code(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,c,p;
		cin>>x>>y>>c>>p;
		komsu[x][c].pb({y,p});
		komsu[y][c].pb({x,p});
		mp[x][c]+=p;
		mp[y][c]+=p;
	}
	priority_queue<pair<ll,pair<int,int>>>pq;
	pq.push({0,{1,0}});
	while(pq.size()){
		ll cos=-pq.top().fr;
		int pos=pq.top().sc.fr,renk=pq.top().sc.sc;
		pq.pop();
		if(renk==0){
			if(vis[pos])continue;
			vis[pos]=1;
			if(pos==n){
				cout<<cos;
				return;
			}
		}
		else{
			if(dp[pos][renk])continue;
			dp[pos][renk]=1;
		}
		if(renk){
			for(auto x:komsu[pos][renk]){
				if(vis[x.fr]==0){
					pq.push({-(cos+mp[pos][renk]-x.sc),{x.fr,0}});
				}
			}
		}
		else{
			for(auto [x,z]:komsu[pos]){
				for(auto y:z){
					if(vis[y.fr]==0){
						pq.push({-(cos+min(y.sc,mp[pos][x]-y.sc)),{y.fr,0}});
					}
					if(dp[y.fr][x]==0){
						pq.push({-(cos),{y.fr,x}});
					}
				}
			}
		}
	}
	cout<<-1;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
	int t=1;
	if(!t)cin>>t;
	while(t--){code();cout<<endl;}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:73:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:73:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42