oj.uz

답안 #758488

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
758488 2023-06-14T16:37:01 Z 1075508020060209tc Robot (JOI21_ho_t4) C++14
24 / 100
 1156 ms 107632 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];
        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;int cnt=2;
        for(int j=0;j<mpe[v][clr[id]].size();j++){
            //    cout<<nw<<" "<<id<<endl;
            cnt--;
            if(cnt<0){break;}
            if(id!=mpe[v][clr[id]][j].second){
                int neid=mpe[v][clr[id]][j].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],vv});
                }
            }


        }

    }



}



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:57:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int j=0;j<mpe[v][clr[id]].size();j++){
      |                     ~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 47316 KB Output is correct
2 Correct 26 ms 47200 KB Output is correct
3 Correct 26 ms 47316 KB Output is correct
4 Correct 23 ms 47316 KB Output is correct
5 Correct 23 ms 47256 KB Output is correct
6 Correct 26 ms 47324 KB Output is correct
7 Correct 25 ms 47444 KB Output is correct
8 Correct 24 ms 47480 KB Output is correct
9 Correct 26 ms 47828 KB Output is correct
10 Correct 26 ms 47780 KB Output is correct
11 Correct 26 ms 47568 KB Output is correct
12 Incorrect 25 ms 47584 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 280 ms 66748 KB Output is correct
2 Correct 111 ms 56924 KB Output is correct
3 Correct 416 ms 69072 KB Output is correct
4 Correct 181 ms 60500 KB Output is correct
5 Correct 1156 ms 107632 KB Output is correct
6 Correct 1044 ms 99776 KB Output is correct
7 Correct 613 ms 85872 KB Output is correct
8 Correct 585 ms 86940 KB Output is correct
9 Correct 637 ms 86820 KB Output is correct
10 Correct 474 ms 80152 KB Output is correct
11 Correct 271 ms 70476 KB Output is correct

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 47316 KB Output is correct
2 Correct 26 ms 47200 KB Output is correct
3 Correct 26 ms 47316 KB Output is correct
4 Correct 23 ms 47316 KB Output is correct
5 Correct 23 ms 47256 KB Output is correct
6 Correct 26 ms 47324 KB Output is correct
7 Correct 25 ms 47444 KB Output is correct
8 Correct 24 ms 47480 KB Output is correct
9 Correct 26 ms 47828 KB Output is correct
10 Correct 26 ms 47780 KB Output is correct
11 Correct 26 ms 47568 KB Output is correct
12 Incorrect 25 ms 47584 KB Output isn't correct
13 Halted 0 ms 0 KB -