Submission #1092998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092998		PieArmy	Robot (JOI21_ho_t4)	C++17	34 / 100	3014 ms	289472 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;}

struct adj{
	int x,c,idx;
	ll p;
	adj(int X,int C,int P,int IDX){
		x=X;
		c=C;
		p=P;
		idx=IDX;
	}
};

int n,m;
int C[200001],P[200001];
vector<adj>komsu[100001];
ll vis[300001];

void code(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y>>C[i]>>P[i];
		adj a(y,C[i],P[i],i);
		komsu[x].pb(adj(y,C[i],P[i],i));
		komsu[y].pb(adj(x,C[i],P[i],i));
	}
	for(ll &x:vis)
		x=-1;
	priority_queue<pair<ll,pair<int,int>>>pq;
	pq.push({0,{1,0}});
	ll ans=inf;
	while(pq.size()){
		ll cos=-pq.top().fr;
		int pos=pq.top().sc.fr,idx=pq.top().sc.sc;
		pq.pop();
		if(idx){
			if(vis[n+idx]!=-1)continue;
			vis[n+idx]=cos;
		}
		else{
			if(vis[pos]!=-1)continue;
			vis[pos]=cos;
		}
		if(pos==n)ans=min(ans,cos);
		map<int,ll>mp;
		for(adj &x:komsu[pos]){
			if(idx!=x.idx)mp[x.c]+=x.p;
		}
		for(adj &x:komsu[pos]){
			if(idx==x.idx)continue;
			if(vis[x.x]==-1){
				pq.push({-(cos+mp[x.c]-x.p),{x.x,0}});
			}
			if(vis[n+x.idx]!=-1)continue;
			pq.push({-(cos+x.p),{x.x,x.idx}});
		}
	}
	if(ans==inf)cout<<-1;
	else cout<<ans;
}

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:76:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:76:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~

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