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 |
|
|
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 |