QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #384203 | #3704. Travel | ucup-team1251 | AC ✓ | 68ms | 33236kb | C++17 | 2.1kb | 2024-04-09 20:56:38 | 2024-04-09 20:56:39 |
Judging History
answer
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<math.h>
#include<set>
#include<unordered_map>
#include<deque>
#define int long long
//__builtin_popcount();
//next_permutation（start,end）和prev_permutation（start,end）
using namespace std;
typedef pair<int, int>PII;
const int N = 1e6+ 10, M = 5e2 + 10;
int n,m,t1,t2;
int h[N],ne[N],e[N],idx,d[N],st[N];
void add(int x,int y)
{
ne[idx]=h[x];
e[idx]=y;
h[x]=idx++;
}
void dd()
{
for(int i=1;i<=n;i++)
{
d[i]=2e10;
st[i]=0;
}
d[1]=0;
queue<PII>q;
q.push({1,0});
while(q.empty()==0)
{
PII tt=q.front();
q.pop();
int x=tt.first;
int y=tt.second;
if(x==n)break;
if(st[x])continue;
st[x]=1;
for(int i=h[x];i!=-1;i=ne[i])
{
int j=e[i];
if(d[j]>y+1)
{
d[j]=y+1;
q.push({j,d[j]});
}
}
}
int tt=d[n]*t1;
int ans=min(tt,t2);
printf("%lld\n",ans);
}
void ff()
{
for(int i=1;i<=n;i++)d[i]=0x3f3f3f3f;
d[1]=0;
set<int>st,op;
set<int>::iterator it;
for(int i=2;i<=n;i++)st.insert(i);
queue<int>q;
q.push(1);
while(q.empty()==0)
{
int x=q.front();
q.pop();
for(int i=h[x];i!=-1;i=ne[i])
{
int j=e[i];//当前有边的
if(st.count(j)!=0)
{
st.erase(j);//当前不能用，但是后面能用
op.insert(j);//下次用
}
}
for(it=st.begin();it!=st.end();it++)
{
q.push(*it);
d[*it]=d[x]+1;//在前面的基础上加上;
}
st.swap(op);
op.clear();
}
int tt=d[n]*t2;
int ans=min(t1,tt);
printf("%lld\n",ans);
}
void df()
{
while(scanf("%lld",&n)!=EOF)
{
scanf("%lld%lld%lld",&m,&t1,&t2);
int flag=0;
memset(h,-1,sizeof(h));
idx=0;
while(m--)
{
int x,y;
scanf("%lld%lld",&x,&y);
if(x>y)swap(x,y);
if(x==1&&y==n)flag=1;
add(x,y);
add(y,x);
}
if(flag==0)
{
if(t2<=t1)printf("%lld\n",t2);
else
dd();
}
else
{
if(t1<=t2)printf("%lld\n",t1);
else ff();
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
df();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 19604kb
input:
3 2 1 3 1 2 2 3
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 17776kb
input:
3 2 2 3 1 2 2 3
output:
3
result:
ok 1 number(s): "3"
Test #3:
score: 0
Accepted
time: 0ms
memory: 13756kb
input:
2 0 1 1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 2ms
memory: 16228kb
input:
2 0 1 1000000000
output:
1000000000
result:
ok 1 number(s): "1000000000"
Test #5:
score: 0
Accepted
time: 0ms
memory: 15852kb
input:
100 2000 348125329 153783443 72 45 79 6 13 64 27 3 22 13 1 76 33 87 72 41 41 30 10 3 43 46 12 40 40 86 38 34 92 96 16 70 11 95 26 78 54 43 50 49 55 82 18 67 49 58 85 41 34 94 57 13 40 44 34 49 95 77 30 74 77 2 90 76 51 98 5 78 5 43 8 96 66 43 74 23 47 25 7 28 77 86 96 4 99 53 80 88 13 29 9 44 51 44 ...
output:
153783443
result:
ok 1 number(s): "153783443"
Test #6:
score: 0
Accepted
time: 2ms
memory: 16348kb
input:
100 2000 231241457 727332287 93 57 38 67 83 11 37 23 90 1 63 91 98 40 48 68 49 83 2 72 57 65 48 94 10 55 71 34 9 50 43 97 62 34 38 10 62 91 2 86 47 74 59 47 62 84 85 81 51 27 6 43 87 21 56 34 48 79 19 54 46 37 98 13 63 48 79 99 38 23 15 48 7 46 13 12 12 31 36 14 35 44 89 60 97 19 80 55 92 70 88 70 2...
output:
231241457
result:
ok 1 number(s): "231241457"
Test #7:
score: 0
Accepted
time: 0ms
memory: 19228kb
input:
100 2000 409324881 595848427 30 6 45 83 92 65 90 4 64 48 5 10 83 85 89 32 6 40 22 54 9 27 51 84 87 55 85 19 37 38 95 75 6 24 53 78 16 28 16 4 33 8 9 32 2 86 70 29 41 12 21 33 24 39 52 22 65 8 36 31 36 81 82 91 81 77 79 21 54 21 57 58 92 8 7 54 2 89 75 49 83 91 74 70 31 57 64 24 34 14 48 68 56 59 52 ...
output:
595848427
result:
ok 1 number(s): "595848427"
Test #8:
score: 0
Accepted
time: 0ms
memory: 18256kb
input:
100 2000 292441009 24173080 45 35 76 39 54 47 69 8 86 14 16 76 65 48 18 7 32 46 56 91 22 32 66 74 68 59 63 59 21 80 85 67 4 38 37 96 4 1 90 20 43 2 13 45 49 28 86 36 22 10 44 64 95 9 64 91 35 61 16 2 49 13 72 85 45 65 78 22 44 59 58 22 44 48 7 13 42 97 21 15 41 45 59 30 98 97 86 7 31 60 94 19 61 66 ...
output:
48346160
result:
ok 1 number(s): "48346160"
Test #9:
score: 0
Accepted
time: 2ms
memory: 16788kb
input:
100 2000 470524433 892689220 70 58 96 74 71 6 16 36 53 5 46 6 63 98 99 2 13 90 79 45 99 47 74 31 80 60 21 15 72 25 51 4 89 85 26 86 15 98 70 35 1 10 37 92 67 48 13 57 91 76 21 81 89 77 50 45 61 69 72 28 40 31 35 97 33 25 41 63 80 36 94 12 48 44 14 93 33 46 50 66 39 50 73 18 35 49 17 59 65 55 40 51 6...
output:
470524433
result:
ok 1 number(s): "470524433"
Test #10:
score: 0
Accepted
time: 0ms
memory: 18892kb
input:
100 2000 108083131 124688303 54 97 16 42 65 15 41 90 15 29 19 36 50 62 55 58 20 9 81 89 60 90 29 54 9 27 69 70 72 88 78 14 13 78 44 91 29 62 19 49 5 44 71 29 66 39 32 37 80 75 75 92 1 37 78 32 67 68 25 51 98 11 29 90 21 60 32 82 64 72 12 72 99 15 4 56 58 23 39 76 28 90 7 100 1 87 39 19 20 6 27 55 85...
output:
124688303
result:
ok 1 number(s): "124688303"
Test #11:
score: 0
Accepted
time: 0ms
memory: 19088kb
input:
100 2000 581133852 993204443 95 24 8 4 29 23 24 42 53 80 94 73 21 54 55 4 10 43 45 7 9 79 59 8 30 39 14 74 74 57 63 5 50 91 66 26 70 77 57 39 5 77 4 5 97 82 76 84 57 12 76 90 52 27 41 68 9 52 49 7 84 64 17 4 69 41 90 55 67 51 38 85 99 45 30 72 21 78 46 55 68 27 91 93 12 74 2 99 38 40 10 69 87 85 81 ...
output:
993204443
result:
ok 1 number(s): "993204443"
Test #12:
score: 0
Accepted
time: 2ms
memory: 17096kb
input:
100 2000 464249980 566753287 37 39 64 97 58 19 57 44 13 83 92 17 99 68 92 35 23 18 79 87 12 11 68 58 33 74 74 46 94 46 88 85 84 31 79 30 3 41 23 15 58 16 7 81 19 79 54 14 36 92 62 55 27 1 80 21 93 86 35 17 16 28 30 62 98 30 59 35 32 20 25 79 6 1 78 25 93 1 36 65 83 81 54 99 7 71 42 50 26 32 34 69 33...
output:
464249980
result:
ok 1 number(s): "464249980"
Test #13:
score: 0
Accepted
time: 0ms
memory: 19148kb
input:
100 2000 642333404 700110644 79 15 29 17 61 40 51 42 79 22 5 47 87 47 66 5 37 15 74 45 83 53 63 82 70 48 52 30 15 84 77 83 98 16 23 21 77 57 50 78 53 96 97 8 18 2 29 4 21 93 26 63 51 63 18 82 35 69 89 61 96 17 75 16 29 11 60 100 23 87 57 56 58 26 99 40 63 45 55 5 36 99 1 3 53 47 64 93 43 5 16 56 69 ...
output:
700110644
result:
ok 1 number(s): "700110644"
Test #14:
score: 0
Accepted
time: 3ms
memory: 16976kb
input:
100 2000 820416828 568626784 69 64 68 63 100 12 10 62 29 36 26 95 13 52 18 32 56 70 18 73 37 59 52 54 26 52 71 62 18 58 27 58 24 19 76 75 68 57 55 22 27 6 64 3 68 35 26 56 67 59 4 15 23 27 22 25 7 35 36 60 12 88 21 41 42 23 75 52 42 7 22 49 56 1 53 57 56 35 60 51 100 75 5 85 2 39 40 81 1 95 50 24 52...
output:
568626784
result:
ok 1 number(s): "568626784"
Test #15:
score: 0
Accepted
time: 3ms
memory: 17612kb
input:
100 2000 353131348 489596917 97 68 46 48 97 63 97 84 67 68 17 6 45 100 49 82 95 94 34 37 36 79 37 55 58 13 39 88 21 36 11 57 16 92 74 53 55 4 9 38 32 29 69 92 36 18 40 32 75 23 28 10 15 38 20 8 53 59 45 48 93 43 75 58 30 11 54 99 18 64 40 83 4 40 12 57 55 86 62 66 26 56 78 85 43 65 84 95 89 85 27 24...
output:
353131348
result:
ok 1 number(s): "353131348"
Test #16:
score: 0
Accepted
time: 2ms
memory: 18332kb
input:
100 2000 826182068 768178465 37 74 5 10 40 9 20 83 85 95 9 56 3 81 46 22 68 94 48 68 15 53 10 35 35 16 100 61 97 82 91 14 27 72 75 30 30 1 90 82 24 77 99 71 74 36 65 79 92 8 83 47 16 4 20 65 66 99 16 22 65 37 22 23 3 65 8 15 31 42 100 33 83 23 58 56 32 46 89 45 89 50 19 96 52 97 55 6 90 20 59 32 55 ...
output:
826182068
result:
ok 1 number(s): "826182068"
Test #17:
score: 0
Accepted
time: 0ms
memory: 19876kb
input:
100 2000 709298197 341727310 75 96 42 89 6 55 65 31 74 44 20 47 86 9 1 73 97 84 22 81 30 61 37 34 79 2 65 27 96 66 85 19 37 45 53 95 9 47 42 71 54 75 31 11 97 77 14 60 18 32 75 72 88 60 45 73 35 48 28 68 1 6 46 2 7 94 12 10 90 54 76 92 56 73 4 98 65 74 38 8 78 5 86 81 33 21 32 13 48 71 97 46 23 32 1...
output:
683454620
result:
ok 1 number(s): "683454620"
Test #18:
score: 0
Accepted
time: 3ms
memory: 19216kb
input:
100 2000 887381621 210243450 46 24 97 53 79 56 23 76 34 54 52 18 16 44 97 75 22 79 37 85 26 78 30 74 51 23 10 55 10 61 38 91 70 27 76 83 4 37 61 87 40 58 79 41 91 61 91 4 33 35 6 68 96 26 51 44 79 55 59 70 24 80 15 54 33 90 42 78 26 57 56 15 68 53 60 18 48 20 40 75 1 100 64 24 46 99 81 41 8 93 32 13...
output:
420486900
result:
ok 1 number(s): "420486900"
Test #19:
score: 0
Accepted
time: 0ms
memory: 16588kb
input:
100 2000 65465045 783792295 11 23 85 12 12 41 20 70 41 59 22 85 21 54 5 34 82 71 23 39 58 91 81 26 61 7 47 45 29 98 72 17 66 56 13 46 49 59 70 74 27 21 69 99 95 24 81 93 65 41 13 94 90 54 83 12 61 56 66 86 50 32 2 31 18 95 39 35 49 12 57 46 94 66 76 93 96 55 17 8 34 71 79 46 18 58 58 37 43 30 85 88 ...
output:
65465045
result:
ok 1 number(s): "65465045"
Test #20:
score: 0
Accepted
time: 3ms
memory: 18940kb
input:
100 2000 848247935 165534481 38 62 17 96 15 43 68 49 4 66 54 83 76 88 63 67 12 31 11 4 64 46 59 78 78 45 73 22 28 11 32 57 45 40 74 40 45 16 37 54 10 25 68 28 77 17 32 8 14 59 75 87 31 67 44 56 92 6 22 76 40 31 56 95 40 98 97 64 99 34 61 68 58 84 43 90 76 84 29 91 12 23 32 69 44 26 50 95 59 55 69 84...
output:
331068962
result:
ok 1 number(s): "331068962"
Test #21:
score: 0
Accepted
time: 2ms
memory: 16092kb
input:
100 2000 321298655 739083325 30 91 87 47 7 8 29 54 33 25 43 3 58 87 54 37 10 92 26 17 76 17 12 84 24 66 11 34 60 54 31 43 55 84 24 10 93 33 94 66 80 89 58 1 7 96 97 40 86 21 6 76 90 59 86 90 18 39 10 14 94 87 16 68 81 13 73 61 72 93 93 85 5 3 69 12 11 14 97 32 66 19 56 96 100 71 41 86 52 53 31 21 89...
output:
321298655
result:
ok 1 number(s): "321298655"
Test #22:
score: 0
Accepted
time: 2ms
memory: 16576kb
input:
100 2000 204414783 607599466 11 79 92 2 26 49 15 34 52 58 88 51 75 98 74 43 15 14 22 76 76 46 18 22 20 35 47 5 77 8 80 65 62 12 25 22 49 51 57 98 21 19 72 9 61 84 63 37 31 34 78 83 11 51 96 10 86 90 20 81 44 41 8 27 82 95 96 6 100 74 91 56 26 76 5 89 73 93 75 87 41 65 20 70 4 75 95 4 64 44 45 54 19 ...
output:
204414783
result:
ok 1 number(s): "204414783"
Test #23:
score: 0
Accepted
time: 2ms
memory: 19272kb
input:
100 2000 382498207 181148310 72 31 21 27 53 92 90 69 13 1 21 71 13 87 61 56 23 13 15 47 5 50 75 65 19 43 80 42 81 35 97 39 10 76 34 21 33 16 36 91 91 60 99 91 86 91 43 21 61 38 7 84 73 83 90 52 68 99 22 59 51 39 64 57 17 6 51 69 17 59 45 2 9 63 98 57 95 36 62 36 30 9 5 36 30 91 66 51 10 50 43 6 8 17...
output:
362296620
result:
ok 1 number(s): "362296620"
Test #24:
score: 0
Accepted
time: 2ms
memory: 17632kb
input:
100 2000 265614335 459729858 37 100 14 72 83 16 84 64 57 43 6 85 96 37 50 65 62 14 69 11 27 49 62 37 9 25 16 9 29 93 4 56 72 78 56 16 21 23 62 50 28 87 26 13 68 75 100 36 17 23 51 100 59 42 72 19 8 48 22 23 77 86 75 94 7 87 86 36 100 77 19 98 53 58 100 49 76 60 40 8 47 82 68 49 42 57 59 68 53 42 67 ...
output:
265614335
result:
ok 1 number(s): "265614335"
Test #25:
score: 0
Accepted
time: 68ms
memory: 33236kb
input:
100000 500000 250533192 794046726 25667 65174 16986 39765 88179 94689 6381 14240 85225 63133 54587 32759 13382 94658 69401 80204 9396 72965 53952 42648 28745 68285 99456 6650 77272 77077 14503 54986 25251 20257 44532 15755 89100 68462 63109 58249 17363 68336 6120 75020 12400 39728 39836 9101 81600 4...
output:
794046726
result:
ok 1 number(s): "794046726"
Test #26:
score: 0
Accepted
time: 57ms
memory: 27848kb
input:
100000 500000 78215009 715016859 21987 52977 32283 24515 92671 43871 81103 551 17572 81480 56441 25872 88315 66381 53556 87559 85707 7734 16458 78222 61128 28480 69246 31261 20529 14776 12996 6719 58827 23024 8982 12377 54587 22367 54022 60288 31151 33804 61241 4675 45819 81229 33166 71576 57757 232...
output:
78215009
result:
ok 1 number(s): "78215009"
Test #27:
score: 0
Accepted
time: 50ms
memory: 27660kb
input:
100000 500000 176389021 736689779 32422 88401 78663 29425 68017 82064 41768 15614 76300 80239 42768 87092 14074 1 72007 167 14191 90935 77398 16627 27817 89276 53938 1 67099 51408 31822 82374 90131 51901 42483 38439 17289 59735 11285 80980 88486 65219 12950 100000 1 25498 63130 67303 100000 36925 85...
output:
176389021
result:
ok 1 number(s): "176389021"