Submission #991756

#	Time	Username	Problem	Language	Result	Execution time	Memory
991756		vjudge1	Toll (APIO13_toll)	C++17	0 / 100	1 ms	4184 KiB

toll

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 5;
vector<pair<int,int> > Greedy, G[N];
bool pro[N];
ll sm[N], p[N];
int n, m, k;


int main()
{
  cin >> n >> m >> k;

  for(int i = 0; i < m; i ++)
    {
      int u, v, w;
      cin >> u >> v >> w;
      G[u].push_back({w, v});
      G[v].push_back({w, u});
      
    }
  
  for(int i = 0; i < k; i ++)
    {
      int u, v;
      cin >> u >> v;
      Greedy.push_back({u, v});
    }

  for(int i = 1; i <= n; i ++)
    cin >> p[i];
  
  ll ans = 0;
  set<pair<int,pair<int,int> > > s;
  s.insert({0, {1, 0}});
 
  while(s.size())
    {
      int u = s.begin()->second.second;
      int v = s.begin()->second.first, w = s.begin()->first;
      s.erase(s.begin());
      if(pro[v]) continue;
      // cerr << v << endl;
      sm[v] = sm[u];
      for(int i = 0; i < k; i ++)
	{
	  if(Greedy[i].first == v && pro[Greedy[i].second] ||
	     pro[Greedy[i].first] && Greedy[i].second == v)
	    {
	      int o = Greedy[i].first + Greedy[i].second - v;
	      if(sm[o] + w >= sm[v])
		sm[v] = sm[o] + w;
	    }
	}
      pro[v] = true;
      ans += sm[v] * p[v];
      // cerr << "sm[" << v << "] = " << sm[v] << endl;
      for(auto [l, r] : G[v])
	s.insert({l, {r, v}});
      
    }
  cout << ans << endl;
  return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:51:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   51 |    if(Greedy[i].first == v && pro[Greedy[i].second] ||

• Subtask 1: 0 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22