Submission #758369

#	Time	Username	Problem	Language	Result	Execution time	Memory
758369		1075508020060209tc	Robot (JOI21_ho_t4)	C++14	34 / 100	3099 ms	50076 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long

int n;int m;
int ar[200005];int br[200005];int clr[200005];int wr[200005];
vector<int>e[200005];

vector<int>dis[200005];
vector<int>vis[200005];
signed main(){
    
cin.tie(0);
ios_base::sync_with_stdio(0);
        
cin>>n>>m;
for(int i=1;i<=m;i++){
    cin>>ar[i]>>br[i]>>clr[i]>>wr[i];
    e[ar[i]].push_back(i);
    e[br[i]].push_back(i);
    dis[ar[i]].push_back(1e18);
    vis[ar[i]].push_back(0);
    dis[br[i]].push_back(1e18);
    vis[br[i]].push_back(0);
}
for(int i=1;i<=n;i++){
    dis[i].push_back(1e18);
    vis[i].push_back(0);
}

priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>> >,greater<pair<int,pair<int,int>>>>pq;
pq.push({0,{1,e[1].size()}});
dis[1][e[1].size()]=0;
while(pq.size()){
    int nw=pq.top().second.first;
    int nwc=pq.top().second.second;
    pq.pop();
    if(vis[nw][nwc]){continue;}
    vis[nw][nwc]=1;
 //   cout<<nw<<" "<<nwc<<endl;
    map<int,int>mpsm;
    for(int i=0;i<e[nw].size();i++){
        if(i==nwc){continue;}
        int id=e[nw][i];
        mpsm[clr[id]]+=wr[id];
    }
    for(int i=0;i<e[nw].size();i++){
        int id=e[nw][i];
        if(i==nwc){continue;}
        int v=ar[id]^br[id]^nw;
        int w=wr[id];
        int eid=lower_bound(e[v].begin(),e[v].end(),id)-e[v].begin();
        if(dis[v][eid]>dis[nw][nwc]+w){
            dis[v][eid]=dis[nw][nwc]+w;
            pq.push({dis[v][eid],{v,eid}});
        }
        w=mpsm[clr[id]]-wr[id];
        eid=e[v].size();
        if(dis[v][eid]>dis[nw][nwc]+w){
            dis[v][eid]=dis[nw][nwc]+w;
            pq.push({dis[v][eid],{v,eid}});
        }
     //   cout<<"hihi\n";
    }
}

int ans=dis[n][0];
for(int i=0;i<=e[n].size();i++){
    ans=min(ans,dis[n][i]);
}
if(ans>=1e18){
    ans=-1;
}

cout<<ans<<endl;

}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:42:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
Main.cpp:47:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
Main.cpp:68:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 | for(int i=0;i<=e[n].size();i++){
      |             ~^~~~~~~~~~~~~

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