| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 584854 |
2022-06-28T05:25:40 Z |
조영욱(#8382) |
도장 모으기 (JOI14_stamps) |
C++14 |
|
1 ms |
596 KB |
#include <bits/stdc++.h>
using namespace std;
int n,m,t,l;
typedef pair<long long,long long> P;
vector<P> adj[4001];
int arr[100001];
long long dp[100001];
long long dp0[100001];
int pos[100001];
bool vis[4001];
long long dist[4001];
const long long INF=1e18;
long long c[2002];
long long d[2002];
typedef pair<P,int> Pi;
typedef pair<P,P> PP;
void dijk(int st,int en,int a,int b) {
priority_queue<P,vector<P>,greater<P>> pq;
pq.push(P(0,st));
for(int i=1;i<=n+1;i++) {
vis[i]=false;
dist[i]=INF;
}
dist[st]=0;
while (!pq.empty()) {
P now=pq.top();
pq.pop();
if (vis[now.second]) {
continue;
}
//printf("..%d\n",now.second);
vis[now.second]=true;
if (now.second==en) {
continue;
}
for(int i=0;i<adj[now.second].size();i++) {
int nt=adj[now.second][i].first;
if (now.second==a&&nt==b) {
continue;
}
if (nt==a&&now.second==b) {
continue;
}
if (dist[nt]>dist[now.second]+adj[now.second][i].second) {
dist[nt]=dist[now.second]+adj[now.second][i].second;
pq.push(P(dist[nt],nt));
//printf("%d %lld %d %lld %lld\n",now.second,dist[nt],nt,dist[now.second],adj[now.second][i].second);
}
}
}
}
int main(void) {
scanf("%d %d %d %d",&n,&m,&t,&l);
for(int i=0;i<m;i++) {
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
adj[u].push_back(P(v,w));
adj[v].push_back(P(u,w));
}
for(int i=1;i<=n;i++) {
c[i]=INF;
for(int j=0;j<adj[i].size();j++) {
int nt=adj[i][j].first;
dijk(i,nt,i,nt);
c[i]=min(c[i],dist[nt]+adj[i][j].second);
}
}
for(int i=1;i<=l;i++) {
scanf("%d",&arr[i]);
}
int p,q;
scanf("%d %d",&p,&q);
arr[p]=q;
dp[1]=0;
dp0[1]=0;
pos[1]=arr[1];
for(int i=2;i<=l;i++) {
int now=arr[i];
if (i!=l&&adj[now].size()==1) {
printf("-1");
return 0;
}
adj[n+1].clear();
for(int i=1;i<=n;i++) {
adj[n+1].push_back(P(i,c[i]));
for(int j=0;j<adj[i].size();j++) {
adj[i][j].second*=2;
}
}
dijk(n+1,now,0,0);
for(int i=1;i<=n;i++) {
d[i]=dist[i];
for(int j=0;j<adj[i].size();j++) adj[i][j].second/=2;
}
vector<long long> vec(adj[now].size());
dijk(arr[i-1],arr[i],0,0);
for(int j=0;j<adj[now].size();j++) {
int nt=adj[now][j].first;
vec[j]=dist[nt]+adj[now][j].second+dp0[i-1];
}
dijk(arr[i-1],arr[i],pos[i-1],arr[i-1]);
for(int j=0;j<adj[now].size();j++) {
int nt=adj[now][j].first;
if (nt==arr[i-1]&&arr[i]==pos[i-1]) {
continue;
}
vec[j]=min(vec[j],dist[nt]+adj[now][j].second+dp[i-1]);
}
long long mn=INF;
int ind=now;
for(int j=0;j<adj[now].size();j++) {
int nt=adj[now][j].first;
if (vec[j]<mn) {
ind=nt;
mn=vec[j];
}
}
long long mn2=INF;
for(int j=0;j<adj[now].size();j++) {
int nt=adj[now][j].first;
if (adj[now][j].first!=ind) {
mn2=min(mn2,vec[j]);
mn2=min(mn2,mn+d[nt]+adj[now][j].second*2);
}
}
long long co=INF;
for(int bit=0;bit<9;bit++) {
vector<PP> save;
vector<int> target;
vector<P> pr=adj[now];
for(int j=0;j<adj[now].size();j++) {
if ((j+save.size())&(1<<bit)) {
int nt=adj[now][j].first;
if (nt==ind) {
continue;
}
adj[now].erase(adj[now].begin()+j);
for(int k=0;k<adj[nt].size();k++) {
if (adj[nt][k].first==now) {
adj[nt].erase(adj[nt].begin()+k);
save.push_back(PP(P(now,nt),P(adj[now][j].second,k)));
break;
}
}
j--;
}
}
adj[now]=pr;
reverse(save.begin(),save.end());
dijk(now,0,now,ind);
for(int j=0;j<save.size();j++) {
adj[save[j].first.second].insert(adj[save[j].first.second].begin()+save[j].second.second,P(save[j].first.first,save[j].second.first));
co=min(co,dist[save[j].first.second]+save[j].second.first);
}
}
dp[i]=mn;
dp0[i]=min(mn2,mn+co);
pos[i]=ind;
//printf("%lld %lld %d\n",dp[i],dp0[i],ind);
}
printf("%lld",dp[l]>=INF?-1:dp[l]);
}
Compilation message
stamps.cpp: In function 'void dijk(int, int, int, int)':
stamps.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i=0;i<adj[now.second].size();i++) {
| ~^~~~~~~~~~~~~~~~~~~~~~~
stamps.cpp: In function 'int main()':
stamps.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int j=0;j<adj[i].size();j++) {
| ~^~~~~~~~~~~~~~
stamps.cpp:89:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int j=0;j<adj[i].size();j++) {
| ~^~~~~~~~~~~~~~
stamps.cpp:96:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int j=0;j<adj[i].size();j++) adj[i][j].second/=2;
| ~^~~~~~~~~~~~~~
stamps.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for(int j=0;j<adj[now].size();j++) {
| ~^~~~~~~~~~~~~~~~
stamps.cpp:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int j=0;j<adj[now].size();j++) {
| ~^~~~~~~~~~~~~~~~
stamps.cpp:114:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(int j=0;j<adj[now].size();j++) {
| ~^~~~~~~~~~~~~~~~
stamps.cpp:122:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for(int j=0;j<adj[now].size();j++) {
| ~^~~~~~~~~~~~~~~~
stamps.cpp:134:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for(int j=0;j<adj[now].size();j++) {
| ~^~~~~~~~~~~~~~~~
stamps.cpp:141:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for(int k=0;k<adj[nt].size();k++) {
| ~^~~~~~~~~~~~~~~
stamps.cpp:154:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | for(int j=0;j<save.size();j++) {
| ~^~~~~~~~~~~~
stamps.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d %d %d %d",&n,&m,&t,&l);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
stamps.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d %d %d",&u,&v,&w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
stamps.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | scanf("%d",&arr[i]);
| ~~~~~^~~~~~~~~~~~~~
stamps.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | scanf("%d %d",&p,&q);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
528 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
