oj.uz

답안 #991753

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
991753 2024-06-03T05:18:28 Z KaleemRazaSyed 통행료 (APIO13_toll) C++17
0 / 100
 1 ms 4184 KB 
#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;
  for(auto [w, v] : G[1])
    s.insert({w, {v, 1}});
  pro[1] = true;
  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;

      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

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

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4184 KB Output isn't correct
2 Halted 0 ms 0 KB -