# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
853304 |
2023-09-24T03:26:04 Z |
future |
Robot (JOI21_ho_t4) |
C++17 |
|
3000 ms |
1453424 KB |
#include <bits/stdc++.h>
using namespace std;
int n,m;
long long dp[100005];
vector<pair<int,long long>>g[100005];
map<int,long long>color[100005];
vector<array<int,4>>save;
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>pq;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1; i<=m; i++) {
int u,v,c,p;
cin>>u>>v>>c>>p;
color[u][c]+=p;
color[v][c]+=p;
save.push_back({u,v,c,p});
}
for(auto [u,v,c,p]:save) {
long long minn=1e18;
minn=min(minn,color[u][c]-p);
for(int i=1; i<=m; i++)minn=min(minn,color[u][i]+p);
g[u].push_back({v,minn});
minn=1e18;
minn=min(minn,color[v][c]-p);
for(int i=1; i<=m; i++)minn=min(minn,color[v][i]+p);
g[v].push_back({u,minn});
}
for(int i=1; i<=n; i++)dp[i]=1e18;
dp[1]=0;
pq.push({0,1});
while(pq.size()) {
auto[_,u]=pq.top();
pq.pop();
if(dp[u]!=_)continue;
for(auto v:g[u])
if(dp[v.first]>dp[u]+v.second) {
dp[v.first]=dp[u]+v.second;
pq.push({dp[v.first],v.first});
}
}
if(dp[n]==1e18)cout<<-1;
else cout<<dp[n];
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7256 KB |
Output is correct |
2 |
Correct |
2 ms |
7260 KB |
Output is correct |
3 |
Correct |
2 ms |
7516 KB |
Output is correct |
4 |
Correct |
2 ms |
7348 KB |
Output is correct |
5 |
Correct |
3 ms |
7772 KB |
Output is correct |
6 |
Correct |
2 ms |
7516 KB |
Output is correct |
7 |
Correct |
55 ms |
11060 KB |
Output is correct |
8 |
Correct |
11 ms |
9048 KB |
Output is correct |
9 |
Incorrect |
516 ms |
132532 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3178 ms |
1453424 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7256 KB |
Output is correct |
2 |
Correct |
2 ms |
7260 KB |
Output is correct |
3 |
Correct |
2 ms |
7516 KB |
Output is correct |
4 |
Correct |
2 ms |
7348 KB |
Output is correct |
5 |
Correct |
3 ms |
7772 KB |
Output is correct |
6 |
Correct |
2 ms |
7516 KB |
Output is correct |
7 |
Correct |
55 ms |
11060 KB |
Output is correct |
8 |
Correct |
11 ms |
9048 KB |
Output is correct |
9 |
Incorrect |
516 ms |
132532 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |