跳到主要内容

单源最短路的建图方式

AcWing 1128. 信使​

题目​

https://www.acwing.com/problem/content/1130/ 战争时期，前线有 n 个哨所，每个哨所可能会与其他若干个哨所之间有通信联系。信使负责在哨所之间传递信息，当然，这是要花费一定时间的（以天为单位）。指挥部设在第一个哨所。当指挥部下达一个命令后，指挥部就派出若干个信使向与指挥部相连的哨所送信。当一个哨所接到信后，这个哨所内的信使们也以同样的方式向其他哨所送信。信在一个哨所内停留的时间可以忽略不计。直至所有 n 个哨所全部接到命令后，送信才算成功。 因为准备充足，每个哨所内都安排了足够的信使（如果一个哨所与其他 k 个哨所有通信联系的话，这个哨所内至少会配备 k 个信使）。现在总指挥请你编一个程序，计算出完成整个送信过程最短需要多少时间。

思路​

本题意思可以转换为：求从原点出发，到所有点距离的最大值， 三种求最短路的算法都可以使用，可以使用书写最简单的floyd算法。

代码​

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N=110,INF=0x3f3f3f3f;

int n,m;
int d[N][N];

int main()
{
	cin>>n>>m;
	memset(d,0x3f,sizeof d);
	for(int i=1;i<=n;i++) d[i][i]=0;

	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		d[a][b]=d[b][a]=min(d[a][b],c);
	}

	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

	int res=0;
	for(int i=1;i<=n;i++)
	{
		if(d[1][i]>INF/2)
		{
			res=-1;
			break;
		}
		else res=max(res,d[1][i]);
	}
	cout<<res;
	return 0;
}

AcWing 1127. 香甜的黄油​

题目​

https://www.acwing.com/problem/content/1129/ 把糖放在一片牧场上，他知道 N 只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。农夫John很狡猾，他知道可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。 数据保证至少存在一个牧场和所有牛所在的牧场连通。

思路​

开一个数组id[]用来记录奶牛，res[]表示所有牛到第i个牧场的距离和 遍历数组id[]，对每头牛做一次Dijkstra算法，然后把距离加到res里面， 最后再遍历res，求最小值即可

代码​

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;

typedef long long LL;

const int N=810,M=3000,INF=0x3f3f3f3f;

int n,m,c;
int h[N],e[M],ne[M],w[M],idx;
int id[N];
int dist[N];
bool st[N];
int res[N];

void add(int a,int b,int c)
{
	w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dijkstra(int start)
{
	memset(dist,0x3f,sizeof dist);
	memset(st,0,sizeof st);

	priority_queue<PII,vector<PII>,greater<PII>> heap;
	dist[start]=0;
	heap.push({0,start});

	while(heap.size())
	{
		PII t=heap.top();heap.pop();
		int u=t.second,distance=t.first;
		if(st[u]) continue;
		st[u]=true;
		for(int i=h[u];~i;i=ne[i])
		{
			int j=e[i];
			if(dist[j]>dist[u]+w[i])
			{
				dist[j]=dist[u]+w[i];
				heap.push({dist[j],j});
			}
		}
	}

	for(int i=1;i<=n;i++)
	{
		if(dist[i]==INF) res[i]=INF;
		else res[i]+=dist[i];
	}

}

int main()
{
	cin>>c>>n>>m;
	memset(h,-1,sizeof h);
	for(int i=0;i<c;i++) cin>>id[i];
	for(int i=0;i<m;i++)
	{
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z),add(y,x,z);
	}
	for(int i=0;i<c;i++) dijkstra(id[i]);

	int ans=INF;
	for(int i=1;i<=n;i++)
	{
		ans=min(ans,res[i]);
	}
	cout<<ans<<endl;
	return 0;
}

AcWing 1126. 最小花费​

题目​

https://www.acwing.com/problem/content/1128/ 在 n 个人中，某些人的银行账号之间可以互相转账。 这些人之间转账的手续费各不相同。 给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问 A 最少需要多少钱使得转账后 B 收到 100 元。

思路​

设刚开始的钱是x,每两个人之间的交易率 则100=x∗(w1∗w2∗w3..)100=x∗(w1∗w2∗w3..)100=x∗(w1∗w2∗w3..)100=x∗(w1∗w2∗w3..) 要想x最小，就要求w1∗w2∗w3..w1∗w2∗w3..w1∗w2∗w3..w1∗w2∗w3..最大 即求log(w1∗w2∗w3..)=log(w1)+log(w2)+..log(w1∗w2∗w3..)=log(w1)+log(w2)+..log(w1∗w2∗w3..)=log(w1)+log(w2)+..log(w1∗w2∗w3..)=log(w1)+log(w2)+..最大， 因为w都是小于1的，所以log(w)都是小于0的，所以将每个数取相反数， 问题转化成求取反后的最小值，即转换成最短路问题

代码​

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
#define sc scanf
#define pr printf

const int N = 2010;

int n, m;
int S, T;
double g[N][N];
double dist[N];
bool st[N];

void dijkstra()
{
	dist[S] = 1;
	for (int i = 1; i <= n; i++)
	{
		int u = i;
		for (int j = 1; j <= n; j++)
		{
			if (!st[j] &&dist[j] > dist[u])
				u = j;
		}
		st[u]=true;

		for(int j=1;j<=n;j++)
		{
			if(dist[j]<dist[u]*g[u][j])
				dist[j]=dist[u]*g[u][j];
		}
	}

}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		double z = (100.0 - c) / 100;
		g[a][b] = g[b][a] = max(g[a][b], z);
	}
	cin>>S>>T;
	dijkstra();
	printf("%.8lf", 100/dist[T]);
	return 0;
}

AcWing 920. 最优乘车​

题目​

https://www.acwing.com/problem/content/922/ H 城是一个旅游胜地，每年都有成千上万的人前来观光。 为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。 每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。 一名旅客最近到 H 城旅游，他很想去 S 公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达 S 公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士，这样换乘几次后到达 S 公园。 现在用整数 1,2,…N 给 H 城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为 1，S 公园巴士站的编号为 N。 写一个程序，帮助这名旅客寻找一个最优乘车方案，使他在从饭店乘车到 S 公园的过程中换乘的次数最少。

思路​

每个车站到达该线路后面的车站的距离都是1，一开始先建图，共需操作Cn2C^2_n 那么1到达n的转车次数==1到达n的最短距离-1

代码​

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define sc scanf
#define pr printf

const int N=510;
int m,n;
bool g[N][N];
int dist[N];
int stop[N];
int q[N];

void bfs()
{
    int hh=0,tt=0;
    memset(dist,0x3f,sizeof dist);
    q[0]=1,dist[1]=0;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=1;i<=n;i++)
        {
            if(g[t][i]&&dist[i]>dist[t]+1)
            {
                dist[i]=dist[t]+1;
                q[++tt]=i;
            }
        }
    }
}

int main()
{
    cin>>m>>n;
    string line;
    getline(cin,line);
    while (m--)
    {
        getline(cin,line);
        stringstream ssin(line);
        int cnt=0,p;
        while(ssin>>p) stop[cnt++]=p;
        for(int j=0;j<cnt;j++)
            for(int k=j+1;k<cnt;k++)
                g[stop[j]][stop[k]]=true;
    }
    
        bfs();
    if(dist[n]==0x3f3f3f3f) cout<<"NO";
    else cout<<max(dist[n]-1,0)<<endl;
    return 0;
}

0%