[C++知识库]C/C++ 租用游艇

租用游艇

题目描述：

样例&数据范围：

思路：

我们把样例画出来

这明显是让我们求最短路呢，把每个出租站看成一个节点，每个节点到另一个节点都有一条有向边，跑一遍迪杰斯特拉就好了。

CODE：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define ll long long
#define INF 0x3f3f3f3f

using namespace std;
ll n, a[210][210];
ll d[210];
bool b[210];
inline ll min1(ll x,ll y){
	return x < y ? x : y;
} 
int main()
{
	//freopen("boat.in", "r", stdin);
	//freopen("boat.out", "w", stdout);
	cin >> n;
	memset(d, 0x3f, sizeof(d));
	memset(a, 0x3f, sizeof(a));
	for (int i = 1; i <= n; ++i) a[i][i] = 0;
	ll t = 1;
	for (int i = 1; i <= n - 1; ++i)
	{
		t = i;
		for (int j = 1; j <= n - i; ++j)
		{
			++t;
			cin >> a[i][t];
			//cout << i << " " << t << endl;
		}
	}
	d[1] = 0;
	for(int i = 1;i <= n - 1;++i)
	{
		ll x = 0;
		for(int j = 1;j <= n;++j)
		{
			if(!b[j]&&(!x||d[j] < d[x])) x = j;
		}
		
		b[x] = 1;
		for(int i = 1;i <= n;++i)
		{
			d[i] = min1(d[i],d[x] + a[x][i]);
		}
	}
	cout << d[n] << endl;
	return 0;
}

感谢您的阅读。