[知识点]-[最短路]

作者：小惠珠哦 | 2024-08-04 15:30:28

踩

[知识点]-[最短路]

单源最短路径

代码：

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e5+10;

int n,m,A;
int dis[N];
int vis[N];

vector<pair<int,int> > e[N];

void spfa()
{
	for(int i=1;i<=n;i++) dis[i] = 1e18;
	queue<int > q;
	q.push(A);
	dis[A] = 0;
	vis[A] = 1;
	while(q.size())
	{
		int now = q.front();
		q.pop();vis[now] = 0;
		for(auto t:e[now])
		{
			int spot = t.first,w = t.second;
			if(dis[spot]>dis[now]+w)
			{
				dis[spot] = dis[now]+w;
				if(vis[spot]==0)
				{
					vis[spot] = 1;
					q.push(spot);
				}
			}
		}
	}	
}

signed main()
{
	cin>>n>>m>>A;
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		e[a].push_back({b,c});
		e[b].push_back({a,c});
	}
	spfa();
	
	for(int i=1;i<=n;i++)
	{
		if(dis[i]==1e18) cout<<(1ll<<31)-1;
		else cout<<dis[i]<<" ";
	}
}
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

spfa判负环1

#include<bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int N = 1e5+10;
 
int n,m,A;
int dis[N];
int vis[N];
int cnt[N];
 
vector<pair<int,int> > e[N];
 
int spfa()
{
    for(int i=1;i<=n;i++) dis[i] = 1e18;
    queue<int > q;
    q.push(n+1);
    dis[n+1] = 0;
    vis[n+1] = 1;
    while(q.size())
    {
        int now = q.front();
        q.pop();vis[now] = 0;
        for(auto t:e[now])
        {
            int spot = t.first,w = t.second;
            if(dis[spot]>dis[now]+w)
            {
                cnt[spot] = cnt[now]+1;
                if(cnt[spot]>=n+1) return false;
                dis[spot] = dis[now]+w;
                if(vis[spot]==0)
                {
                    vis[spot] = 1;
                    q.push(spot);
                }
            }
        }
    }
    return true;
}
 
signed main()
{
    cin>>n>>m;
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        e[a].push_back({b,c});
    }
    for(int i=1;i<=n;i++)
    {
        e[n+1].push_back({i,0});
    }
    spfa()?cout<<"No":cout<<"Yes";
}
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

spfa判负环2

#include<bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int N = 1e5+10;
 
int T,n,m;
int dis[N];
int vis[N];
int cnt[N];
 
vector<pair<int,int> > e[N];
 
int spfa()
{
    queue<int > q;
    q.push(1);
    dis[1] = 0;
    vis[1] = 1;
    while(q.size())
    {
        int now = q.front();
        q.pop();vis[now] = 0;
        for(auto t:e[now])
        {
            int spot = t.first,w = t.second;
            if(dis[spot]>dis[now]+w)
            {
                cnt[spot] = cnt[now]+1;
                if(cnt[spot]>=n) return false;
                dis[spot] = dis[now]+w;
                if(vis[spot]==0)
                {
                    vis[spot] = 1;
                    q.push(spot);
                }
            }
        }
    }
    return true;
}
 
signed main()
{
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
	    for(int i=1;i<=n;i++)
	    {
	    	e[i].clear();
	    	dis[i] = 1e18;
	    	vis[i] = 0;
	    	cnt[i] = 0;
		}
	    while(m--)
	    {
	        int a,b,c;
	        cin>>a>>b>>c;
	        if(c>=0)
	        {
	        	e[a].push_back({b,c});
	        	e[b].push_back({a,c});
			}
			else e[a].push_back({b,c});
	    }
	    spfa()?cout<<"NO\n":cout<<"YES\n";
	}
    return 0;
}
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
71

道路重建

#include<bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int N = 1e5+10;
 
int n,m,d,A,B;
int dis[N];
int vis[N];

map<pair<int,int>,int> mp;
vector<pair<int,int> > e[N];

void spfa()
{
	for(int i=1;i<=n;i++) dis[i] = 1e18;
	queue<int > q;
	q.push(A);
	dis[A] = 0;
	vis[A] = 1;
	while(q.size())
	{
		int now = q.front();
		q.pop();vis[now] = 0; 
		for(auto t:e[now])
		{
			int spot = t.first,w = 0;
			if(mp[{now,spot}]==1) w = t.second;
			if(dis[spot]>dis[now]+w)
			{
				dis[spot] = dis[now]+w;
				if(vis[spot]==0)
				{
					vis[spot] = 1;
					q.push(spot);
				}
			}
		}
	}
}
signed main()
{
	cin>>n>>m;
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		e[a].push_back({b,c});
		e[b].push_back({a,c});
	}
	cin>>d;
	while(d--)
	{
		int a,b;
		cin>>a>>b;
		mp[{a,b}] = 1;
		mp[{b,a}] = 1;
	}
	cin>>A>>B;
	spfa();
	cout<<dis[B];
    return 0;
}
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

拉近距离

#include<bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int N = 1e5+10;
 
int n,m;
int suc = 1;
int dis[N],vis[N],cnt[N];

vector<pair<int,int> > e[N];

int spfa(int A)
{
	for(int i=1;i<=n;i++)
	{
		dis[i] = 1e18;
		vis[i] = 0;
		cnt[i] = 0;
	}
	queue<int > q;
	q.push(A);
	dis[A] = 0;
	vis[A] = 1;
	while(q.size())
	{
		int now = q.front();
		q.pop();vis[now] = 0; 
		for(auto t:e[now])
		{
			int spot = t.first,w = t.second;
			if(dis[spot]>dis[now]-w)
			{
				dis[spot] = dis[now]-w;
				cnt[spot] = cnt[now]+1;
				if(cnt[spot]>=n)
				{
					suc = 0;
					return false;
				}
				if(vis[spot]==0)
				{
					vis[spot] = 1;
					q.push(spot);
				}
			}
		}
	}
	return true;
}

signed main()
{
	cin>>n>>m;
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		e[a].push_back({b,c});
	}
	spfa(1);
	int a = dis[n];
	spfa(n);
	int b = dis[1];
	if(suc==0) cout<<"Forever love";
	else cout<<min(a,b);
    return 0;
}
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

floyd模版

#include<bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int N = 1e5+10;
 
int n,m;
int dis[110][110];

void floyd()
{
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);
		}	
	}	
}

signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			dis[i][j] = 1e18;
			if(i==j) dis[i][j] = 0;
		}
	}
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		dist[a][b] = min(dist[a][b],c);
		dist[b][a] = min(dist[b][a],c);
	}
	floyd();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) cout<<dis[i][j]<<" ";
		cout<<"\n";
	}
    return 0;
}
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

采购特价商品

代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define int long long 
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
 
using namespace std;
 
const int N = 1e5+10;
 
int n,m;
double dis[110][110];

pair<int,int> va[N];

void floyd()
{
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);		
		}
	}	
}

signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>va[i].fi>>va[i].se;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			dis[i][j] = 1e18;
			if(i==j) dis[i][j] = 0;
		}
	}
	cin>>m;
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		double sum = 0;
		sum += (va[a].fi-va[b].fi)*(va[a].fi-va[b].fi);
		sum += (va[a].se-va[b].se)*(va[a].se-va[b].se);
		sum = sqrt(sum);
		dis[a][b] = min(dis[a][b],sum);
		dis[b][a] = min(dis[b][a],sum);
	}
	floyd();
	int s,t;
	cin>>s>>t;
	printf("%.2lf",dis[s][t]);
    return 0;
}
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

单源最短路径（标准版）

代码：

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)


using namespace std;

const int N = 1e5+10;

int n,m,T;
int A,B;
int dist[N],vis[N];

vector<PII > e[N];

void distra()
{
	priority_queue<PII,vector<PII>,greater<PII>> q;
	for(int i=1;i<=n;i++) dist[i] = 1e18;
	q.push({0,A});
	dist[A] = 0;
	while(q.size())
	{
		auto t = q.top();q.pop();
		int now = t.se,dis = t.fi;
		if(vis[now]==1) continue;
		vis[now] = 1;
		for(auto tt:e[now])
		{
			int spot = tt.se,w = tt.fi;
			if(dist[spot]>dist[now]+w)
			{
				dist[spot] = dist[now]+w;
				q.push({dist[spot],spot});
			}
		}
	}
}

signed main()
{
	IOS;
	cin>>n>>m>>A;
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		e[a].pb({c,b});
	}
	distra();
	for(int i=1;i<=n;i++) cout<<dist[i]<<" ";
	return 0;
}
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

小明的游戏

代码：

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define PII pair<int,pair<int,int>>
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

using namespace std;

const int N = 1e5+10,M = 550;

int n,m;
int sx,sy,ex,ey;
char va[M][M];
int vis[M][M];
int dist[M][M];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

void distra()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			dist[i][j] = 1e18;
			vis[i][j] = 0;
		}
	}
	priority_queue<PII,vector<PII>,greater<PII>> q;
	q.push({0,{sx,sy}});
	dist[sx][sy] = 0;
	while(q.size())
	{
		auto t = q.top();q.pop();
		int x = t.se.fi,y = t.se.se;
		if(vis[x][y]==1) continue;
		vis[x][y] = 1;
		for(int i=0;i<=3;i++)
		{
			int xx = x+dx[i],yy = y+dy[i];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m)
			{
				int w = (va[x][y]!=va[xx][yy]);
				if(dist[xx][yy]>dist[x][y]+w)
				{
					dist[xx][yy] = dist[x][y]+w;
					q.push({dist[xx][yy],{xx,yy}});
				}
			}
		}
	}
}

signed main()
{
	while(1)
	{
		cin>>n>>m;
		if(n==0&&m==0) break;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			cin>>va[i][j];
		}
		cin>>sx>>sy>>ex>>ey;
		sx += 1,sy += 1,ex += 1,ey += 1; 
		distra();
		cout<<dist[ex][ey]<<"\n";
	}
}
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
71

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小惠珠哦/article/detail/928433