进阶图论（最短路系列）
题目狂刷
P3371 【模板】单源最短路径（弱化版）
https://www.luogu.com.cn/problem/P3371
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
struct edge
{
int v,w;
};
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,s;
cin>>n>>m>>s;
vector<vector<edge>>adj(n+1);
vector<int>dis(n+1,INT_MAX);
vector<bool>vis(n+1);
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
adj[u].push_back({v,w});
}
dis[s]=0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>>pq;
pq.push({0,s});
while(pq.size())
{
auto [_,u]=pq.top();
pq.pop();
if(vis[u])continue;
vis[u]=1;
for(auto [v,w]:adj[u])
{
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
pq.push({dis[v],v});
}
}
}
for(int i=1;i<=n;i++)cout<<dis[i]<<" \n"[i==n];
return 0;
}
|
P4779 【模板】单源最短路径（标准版）
https://www.luogu.com.cn/problem/P4779
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
struct edge
{
int v,w;
};
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,s;
cin>>n>>m>>s;
vector<vector<edge>>adj(n+1);
vector<int>dis(n+1,INT_MAX);
vector<bool>vis(n+1);
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
adj[u].push_back({v,w});
}
dis[s]=0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>>pq;
pq.push({0,s});
while(pq.size())
{
auto [_,u]=pq.top();
pq.pop();
if(vis[u])continue;
vis[u]=1;
for(auto [v,w]:adj[u])
{
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
pq.push({dis[v],v});
}
}
}
for(int i=1;i<=n;i++)cout<<dis[i]<<" \n"[i==n];
return 0;
}
|
C. Dijkstra?
https://codeforces.com/problemset/problem/20/C
这一道题一直内存超，最后修改了不让v重复入队。这个好像不是set，还是可以重复入队的。
这个pair<int,int>修改的也十分到位，感觉这个很好用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<vector<pair<int,int>>>adj(n+1);
vector<bool>vis(n+1);
vector<int>dis(n+1,INT_MAX);
dis[1]=0;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
adj[u].emplace_back(v,w);
adj[v].emplace_back(u,w);
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>>pq;
pq.push({0,1});
vector<int>fa(n+1);
while(pq.size())
{
auto [_,u]=pq.top();
pq.pop();
if(vis[u])continue;
vis[u]=1;
for(auto [v,w]:adj[u])
{
if(vis[v])continue;
if(dis[u]+w<dis[v])
{
dis[v]=dis[u]+w;
fa[v]=u;
pq.push({dis[v],v});
}
}
}
vector<int>ans;
if(dis[n]==INT_MAX)cout<<-1<<'\n';
else
{
auto dfs=[&](auto self,int x)->void{
if(x==1){cout<<1<<' ';return;}
self(self,fa[x]);
cout<<x<<' ';
};
dfs(dfs,n);
}
return 0;
}
|
P1576 最小花费
https://www.luogu.com.cn/problem/P1576
这一题其实考验的是最长路，这一题其实要求的就是从A到B所消耗的比例最少的路径，我们走的所有路径最终的结果是1*所有得比例，这个结果越大越好，就是最长路。然后就是路径中得加法运算变成乘法运算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<vector<pair<int,double>>>adj(n+1);
vector<double>bei(n+1,-inf);
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
double it=(double)(100-w)/100;
adj[u].emplace_back(v,it);
adj[v].emplace_back(u,it);
}
int a,b;
cin>>a>>b;
bei[a]=1;
priority_queue<pair<double,int>>pq;
pq.push({1,a});
vector<int>vis(n+1);
while(pq.size())
{
auto [bi,u]=pq.top();
pq.pop();
if(vis[u])continue;
vis[u]=1;
for(auto [v,w]:adj[u])
{
if(bei[u]*w>bei[v])
{
bei[v]=bei[u]*w;
pq.push({bei[v],v});
}
}
}
cout<<fixed<<setprecision(8)<<100/bei[b]<<'\n';
return 0;
}
|
P5767 [NOI1997] 最优乘车
https://www.luogu.com.cn/problem/P5767
这道题学会一个好东西
std::ws 是 C++ 标准库中的一个输入流操作符，用于跳过输入流中的所有空白字符（包括空格、制表符和换行符），直到遇到非空白字符为止。
这道题中为了消除行末的空白字符需要用这个，洛谷这道题好像是行末有两个空白字符还是什么情况，快给我卡死了。
1
2
3
4
|
char ch;
cin.get(ch);
cin.get(ch);
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include <bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m, n;
cin >> m >> n;
char ch;
cin>>ws;
vector<vector<pair<int, int>>> adj(n + 1);
vector<bool> vis(n + 1);
vector<int> dis(n + 1, inf);
dis[1] = 0;
for (int i = 1; i <= m; i++)
{
vector<int> a;
string s;
getline(cin,s);
for(int i=0;i<s.size();i++)
{
int x=0;
while(isdigit(s[i]))
{
x=x*10+s[i]-'0';
i++;
}
a.push_back(x);
}
for(int i=0;i<a.size();i++)
{
for(int j=i+1;j<a.size();j++)
{
adj[a[i]].push_back({a[j],1});
}
}
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({0, 1});
while (pq.size())
{
auto [_, u] = pq.top();
pq.pop();
if (vis[u])
continue;
vis[u] = 1;
for (auto [v, w] : adj[u])
{
if (vis[v] == 0 && dis[u] + w < dis[v])
{
dis[v] = dis[u] + w;
pq.push({dis[v], v});
}
}
}
if (dis[n] == inf)
cout << "NO\n";
else
cout << dis[n] - 1 << '\n';
return 0;
}
|
wechat
