最优贸易

输入第一行包含2个正整数n和m，中间用一个空格隔开，分别表示城市的数目和道路的数目。
第二行n个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这n个城市的商品价格。
接下来m行，每行有3个正整数，x,y,z，每两个整数之间用一个空格隔开。如果z=1，表示这条道路是城市x到城市y之间的单向道路；如果z=2，表示这条道路为城市x和城市y之间的双向道路。

C++14(g++5.4) 解法, 执行用时: 135ms, 内存消耗: 2792K, 提交时间: 2019-12-28 21:54:19

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+1;
int n, m;
int price[MAXN];
vector<pair<int, int>> edges;
vector<int> reached;

int gao(int S) {
  vector<int> d(n+1, 0x3f3f3f3f);
  d[S] = price[S];
  int ans = 0;
  for (int i = 0; i < n; i++) {
    bool ok = true;
    for (auto it: edges) {
      int x = it.first, y = it.second;
      if (d[y] > d[x]) d[y] = d[x], ok = false;;
      if (d[x] != 0x3f3f3f3f && d[y] > price[y]) d[y] = price[y], ok = false;
      if (S == 1 && reached[y] != 0x3f3f3f3f) ans = max(ans, price[y] - d[y]);
    }
    if (ok) break;
  }
  if (S == n) reached = d;
  return ans;
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> price[i];
  while (m--) {
    int x, y, z; cin >> x >> y >> z;
    edges.push_back({x, y});
    if (z == 2) edges.push_back({y, x});
  }

  for (auto &it: edges) swap(it.first, it.second);
  gao(n);
  for (auto &it: edges) swap(it.first, it.second);
  cout << gao(1) << endl;
}

C++(g++ 7.5.0) 解法, 执行用时: 68ms, 内存消耗: 7244K, 提交时间: 2023-04-17 17:18:44

#include<bits/stdc++.h>
#define N 100005
#define int long long
using namespace std;
vector<int> d[N];
int n,m,f[N],res[N],cost[N];
void dfs(int now,int mini,int fa){
    bool flag=1;
    mini=min(cost[now],mini);
    if(res[now]>mini){
        res[now]=mini;
        flag=0;
    }
    int maxi=max(f[fa],cost[now]-mini);
    if(f[now]<maxi){
        f[now]=maxi;
        flag=0;
    }
    if(flag){
        return;
    }
    for(int i=0;i<d[now].size();i++){
        dfs(d[now][i],mini,now);
    }
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>cost[i];
    }
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        if(z==1){
            d[x].push_back(y);
        }
        else{
            d[x].push_back(y);
            d[y].push_back(x);
        }
    }
    memset(res,0x3f,sizeof(res));
    dfs(1,0x3f3f3f3f,0);
    cout<<f[n]<<endl;
}

C++ 解法, 执行用时: 50ms, 内存消耗: 5840K, 提交时间: 2022-06-19 19:38:07

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>G[N];
int n,m,f[N],g[N],a[N];
inline void dfs(int x,int v,int p)
{
	bool fl=1;
	v=min(a[x],v);
	if(g[x]>v)
	{
		g[x]=v;
		fl=0;
	}
	int c=max(f[p],a[x]-v);
	if(f[x]<c)
	f[x]=c,fl=0;
	if(fl)return ;
	for(int i=0;i<G[x].size();i++)
	dfs(G[x][i],v,x);
}
int main(){
	scanf("%d%d",&n,&m);
	memset(g,0x3f3f3f3f,sizeof(g));
	for(int i=1; i<=n; i++)
	scanf("%d",&a[i]);
	while(m--)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		G[x].push_back(y);
		if(z==2)
		G[y].push_back(x);
	}
	dfs(1,1e9,0);
	cout<<f[n]<<endl;
	return 0;
}

详情