QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#380120#3704. Travelucup-team1251TL 1ms3828kbC++201.9kb2024-04-06 21:05:282024-04-06 21:06:16

Judging History

This is the latest submission verdict.

  • [2024-04-06 21:06:16]
  • Judged
  • Verdict: TL
  • Time: 1ms
  • Memory: 3828kb
  • [2024-04-06 21:05:28]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define PII pair<int,int>
#define PPI pair<PII,int>
const int N=1e3+5;
int n,m,a,b;
map<PII,int>mp;
vector<int>g[N];
int sum[N],dis[N];
void dij()
{
	for(int i=1;i<=n;i++)
	{
		dis[i]=0;
		sum[i]=0x3f3f3f3f;
	}
	sum[1]=0;
	priority_queue<PII,vector<PII>,greater<PII> >q;
	q.push({0,1});
	while(!q.empty())
	{
		PII f=q.top();
		q.pop();
		int dist=f.first,x=f.second;
		if(x==n)
			return;
		if(dis[x])
			continue;
		dis[x]=1;
		for(int i=0;i<g[x].size();i++)
		{
			if(sum[g[x][i]]>dist+1)
			{
				sum[g[x][i]]=dist+1;
				q.push({sum[g[x][i]],g[x][i]});
			}
		}
	}
}
int djj()
{
	vector<int>p;
	for(int i=2;i<=n;i++)
	{
		p.push_back(i);
	}
	queue<PII>q;
	q.push({0,1});
	while(q.size())
	{
		PII f=q.front();
		q.pop();
		int dist=f.first,x=f.second;
		if(x==n)
			return dist;
		for(auto i=p.begin();i!=p.end();i++)
		{
			if(!mp[{min((*i),x),max((*i),x)}])
			{
				q.push({dist+1,(*i)});
				p.erase(i);
			}
		}
	}
	return 0x3f3f3f3f;
}
void solve(){
	while(cin>>n>>m>>a>>b){
		int u,v;
		for(int i=1;i<=n;i++)
		{
			g[i].clear();
		}
		mp.clear();
		for(int i=1;i<=m;i++)
		{
			cin>>u>>v;
			mp[{min(u,v),max(u,v)}]=1;
			g[v].push_back(u);
			g[u].push_back(v);
		}
		if(a<b)
		{
			if(mp[{1,n}]==1)
			{
				cout<<a<<endl;
				continue;
			}
			dij();
			cout<<min(sum[n]*a,b)<<endl;
		}
		else if(b<a)
		{
			if(!mp[{1,n}])
			{
				cout<<b<<endl;
				continue;
			}
			int ans=djj();
			cout<<min(ans*b,a)<<endl;
		}
		else
		{
			cout<<a<<endl;
		}
	}
} 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
//	vector<int>p;
//	for(int i=1;i<=10;i++)
//		p.push_back(i);
//	
//	for(auto x=p.begin();x!=p.end();x++)
//	{
//		if((*x)==5||(*x)==8)
//		{
//			p.erase(x);
//			cout<<(*x)<<endl;
//		}
//	}
//	for(int i=0;i<p.size();i++)
//	{
//		cout<<p[i]<<" ";
//	}
	solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3552kb

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: 3552kb

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: 3788kb

input:

2 0 1 1

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

2 0 1 1000000000

output:

1000000000

result:

ok 1 number(s): "1000000000"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3812kb

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: 1ms
memory: 3828kb

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: 1ms
memory: 3740kb

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: -100
Time Limit Exceeded

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:


result: