oj.uz

답안 #758462

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
758462 2023-06-14T16:08:50 Z 1075508020060209tc Robot (JOI21_ho_t4) C++14
0 / 100
 967 ms 109084 KB 
#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];
int dis[200005];
int vis[200005];
map<int,int>mpsm[500005];
int mpf[500005];

map<int,vector<pair<int,int>>>mpe[200005];
map<int,int>mxe[200005];
signed main(){


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);
    mpe[ar[i]][clr[i]].push_back({wr[i],i});
    mpe[br[i]][clr[i]].push_back({wr[i],i});
    mpsm[ar[i]][clr[i]]+=wr[i];
    mpsm[br[i]][clr[i]]+=wr[i];
}
for(int i=1;i<=n;i++){
    dis[i]=1e18;
    vis[i]=0;
    for(auto it=mpsm[i].begin();it!=mpsm[i].end();it++){
        sort(mpe[i][(*it).first].begin(),mpe[i][(*it).first].end());
    }
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
dis[1]=0;
pq.push({0,1});
while(pq.size()){
    int nw=pq.top().second;
    pq.pop();
    if(vis[nw]){continue;}
    vis[nw]=1;

    for(int i=0;i<e[nw].size();i++){
        int id=e[nw][i];
     //   mpsm[clr[id]]=0;
        mpf[clr[id]]=0;
    }
    for(int i=0;i<e[nw].size();i++){
        int id=e[nw][i];
       // mpsm[clr[id]]+=wr[id];
        mpf[clr[id]]++;
    }
    for(int i=0;i<e[nw].size();i++){
        int id=e[nw][i];
        int v=ar[id]^br[id]^nw;
        //if(vis[v]){continue;}
        int w=wr[id];
      //  if(mpf[clr[id]]==1){
        //    w=0;
        //}
        if(dis[v]>dis[nw]+min(w,mpsm[nw][clr[id]]-w) ){
            dis[v]=dis[nw]+min(w,mpsm[nw][clr[id]]-w);
            pq.push({dis[v],v});
        }
        int ow=dis[nw]+w;
        if(mpe[v][clr[id]].size()>=2){
            //    cout<<nw<<" "<<id<<endl;
            if(id!=mpe[v][clr[id]].back().second){
                int neid=mpe[v][clr[id]].back().second;
                int vv=v^ar[neid]^br[neid];
                w=mpsm[v][clr[id]]-wr[id]-wr[neid];
             //   cout<<nw<<" "<<v<<" "<<vv<<" "<<neid<<" "<<ow<<" "<<w<<endl;
                if(dis[vv]>ow+w){
                    dis[vv]=ow+w;
                    pq.push({dis[vv],v});
                }
            }
            if(id!=mpe[v][clr[id]][mpe[v][clr[id]].size()-2].second){
                int neid=mpe[v][clr[id]][mpe[v][clr[id]].size()-2].second;
                int vv=v^ar[neid]^br[neid];
                w=mpsm[v][clr[id]]-wr[id]-wr[neid];
                if(dis[vv]>ow+w){
                    dis[vv]=ow+w;
                    pq.push({dis[vv],v});
                }
            }
            
            
            
            
        }

    }



}



int ans=dis[n];
if(dis[n]>=1e16){
    ans=-1;
}


cout<<ans<<endl;

}
/*
6 5
1 2 1 100000
1 3 1 1
2 6 1 1000
2 4 1 1
2 5 1 1
*/

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:44: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]
   44 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
Main.cpp:49: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]
   49 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
Main.cpp:54: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]
   54 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~

Subtask #1
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 47316 KB Output is correct
2 Correct 20 ms 47316 KB Output is correct
3 Correct 24 ms 47272 KB Output is correct
4 Correct 25 ms 47328 KB Output is correct
5 Correct 22 ms 47260 KB Output is correct
6 Correct 22 ms 47276 KB Output is correct
7 Correct 23 ms 47444 KB Output is correct
8 Correct 22 ms 47380 KB Output is correct
9 Incorrect 26 ms 47896 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 295 ms 66728 KB Output is correct
2 Correct 145 ms 56924 KB Output is correct
3 Correct 398 ms 69012 KB Output is correct
4 Correct 194 ms 60576 KB Output is correct
5 Incorrect 967 ms 109084 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 47316 KB Output is correct
2 Correct 20 ms 47316 KB Output is correct
3 Correct 24 ms 47272 KB Output is correct
4 Correct 25 ms 47328 KB Output is correct
5 Correct 22 ms 47260 KB Output is correct
6 Correct 22 ms 47276 KB Output is correct
7 Correct 23 ms 47444 KB Output is correct
8 Correct 22 ms 47380 KB Output is correct
9 Incorrect 26 ms 47896 KB Output isn't correct
10 Halted 0 ms 0 KB -