Submission #588160


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

struct UNKO{
    LL cost,color;
    int zaatu,to;
    UNKO(){to=cost=color=zaatu=-1;}
    UNKO(int t,LL ct,LL cr){to=t,cost=ct,color=cr,zaatu=-1;}
    UNKO(int t,LL ct,LL cr,int z){to=t,cost=ct,color=cr,zaatu=z;}
    bool operator<(const UNKO& l)const{return cost>l.cost;}
    bool operator>(const UNKO& l)const{return cost<l.cost;}
};
const LL INF=((LL)1e9)*(LL)1e6;
LL dijkstra(vector<list<UNKO>>& adj,int s,int N,int g){
    vector<LL> dist(N,INF);
    priority_queue<UNKO> que;
    que.push(UNKO(0,0,1,s));
    while(que.empty()==false){
        UNKO v=que.top();que.pop();
        if(v.cost>=dist[v.zaatu])continue;
        dist[v.zaatu]=v.cost;
        if(v.to==g)return v.cost;
        for(auto& u : adj[v.to]){
            LL cost=v.cost+abs(v.color-u.color)+u.cost;
            if(cost<dist[u.zaatu])
                que.push(UNKO(u.to,cost,u.color,u.zaatu));
        }
    }
    return INF;
}

int main() {
    int N,M;
    scanf("%d %d",&N,&M);
    map<pair<int,LL>,int> zaatu;
    vector<list<UNKO>> adj(N);
    for(int i = 0; i < M; i++){
        int a,b;LL c,t;
        scanf("%d %d %lld %lld",&a,&b,&c,&t);
        a--;b--;
        zaatu[make_pair(a,c)]=0;
        zaatu[make_pair(b,c)]=0;
        adj[a].push_back(UNKO(b,t,c));
        adj[b].push_back(UNKO(a,t,c));
    }
    zaatu[make_pair(0,1ll)]=0;
    int cnt=0;
    for(auto& it : zaatu){
        it.second=cnt++;
    }
    for(auto& it : adj){
        for(auto& jt : it){
            jt.zaatu=zaatu[make_pair(jt.to,jt.color)];
        }
    }
    LL res=dijkstra(adj,zaatu[make_pair(0,1ll)],zaatu.size(),N-1);
    cout<<res<<endl;
    return 0;
}

Submission Info

Submission Time
Task G - カメレオン
User btk15049
Language C++11 (GCC 4.9.2)
Score 100
Code Size 1750 Byte
Status AC
Exec Time 1835 ms
Memory 69732 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:35:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&N,&M);
                         ^
./Main.cpp:40:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %lld %lld",&a,&b,&c,&t);
                                             ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 20
Set Name Test Cases
Sample sample-01.txt, sample-02.txt
All test-01.txt, test-02.txt, test-03.txt, test-04.txt, test-05.txt, test-06.txt, test-07.txt, test-08.txt, test-09.txt, test-10.txt, test-11.txt, test-12.txt, test-13.txt, test-14.txt, test-15.txt, test-16.txt, test-17.txt, test-18.txt, test-19.txt, test-20.txt
Case Name Status Exec Time Memory
sample-01.txt AC 35 ms 1084 KB
sample-02.txt AC 31 ms 1116 KB
test-01.txt AC 32 ms 1140 KB
test-02.txt AC 31 ms 1080 KB
test-03.txt AC 34 ms 1284 KB
test-04.txt AC 38 ms 1780 KB
test-05.txt AC 37 ms 1468 KB
test-06.txt AC 184 ms 13680 KB
test-07.txt AC 387 ms 21520 KB
test-08.txt AC 140 ms 8396 KB
test-09.txt AC 248 ms 16172 KB
test-10.txt AC 45 ms 2364 KB
test-11.txt AC 63 ms 3804 KB
test-12.txt AC 116 ms 7804 KB
test-13.txt AC 388 ms 21524 KB
test-14.txt AC 187 ms 13944 KB
test-15.txt AC 152 ms 11028 KB
test-16.txt AC 156 ms 11064 KB
test-17.txt AC 476 ms 26884 KB
test-18.txt AC 1375 ms 69732 KB
test-19.txt AC 1835 ms 69684 KB
test-20.txt AC 632 ms 32908 KB