accepted
Posted by
Mikhail 13 Jun 2018 21:37
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("avx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define re return
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sqrt(x) sqrt(abs(x))
#define mp make_pair
#define pi (3.14159265358979323846264338327950288419716939937510)
#define fo(i, n) for(int i = 0; i < n; ++i)
#define ro(i, n) for(int i = n - 1; i >= 0; --i)
#define unique(v) v.resize(unique(all(v)) - v.begin())
template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }
template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef double D;
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef unsigned long long ull;
typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree;
const int maxn = 31;
vector <pair<int, ii>> g[maxn][maxn];
int d[maxn][maxn];
bool _sort(ii a, ii b) {
if (d[a.fi][a.se] != d[b.fi][b.se]) re d[a.fi][a.se] < d[b.fi][b.se];
re a < b;
}
set <ii, bool (*) (ii, ii)> s(_sort);
void read (int a, int b) {
int k, x, w;
cin >> k;
fo(i, k) {
cin >> x;
while (x != 0) {
cin >> w ;
g[a][x - 1].pb(mp(b, mp(i, w)));
cin >> x;
}
}
}
void dejkstra() {
fo(i, maxn) fo(j, maxn) d[i][j] = (int) 1e9;
d[0][0] = 0;
int x, y, a, b, w;
s.insert(mp(0, 0));
while (!s.empty()) {
x = (*s.begin()).fi, y = (*s.begin()).se;
s.erase(s.begin());
for (auto &j : g[x][y]) {
a = j.fi, b = j.se.fi, w = j.se.se;
if (d[a][b] > d[x][y] + w) {
s.erase(mp(a, b));
d[a][b] = d[x][y] + w;
s.insert(mp(a, b));
}
}
}
}
int main() {
int n;
cin >> n;
string str;
for (int i = 1; i <= n; ++i) {
read (i - 1, i);
if (i < n) cin >> str;
}
dejkstra();
int ans = (int) 1e9;
fo(i, maxn) ans = min(ans, d[n][i]);
cout << ans << endl;
}
Re: accepted
Posted by
INSOS 11 Nov 2019 03:59
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main()
{
int n;
cin >> n; // quantity of levels in Ivans map
int cs[35][35][35];
vector<int> v[35][35];
int inLevel[35];
for(int i = 1; i <= n; ++i)
{
int k;
cin >> k;
inLevel[i] = k;
for(int j = 1; j <= k; ++j)
{
while(true)
{
int a, b;
cin >> a;
if(a == 0)
{
break;
}
cin >> b;
v[i][j].push_back(a); /// on i-th level to planet "j" we can come from planet "a" in i-1 - th level
cs[i][j][a] = b; /// on i-1-th level planet "a" pay b$ for going to planet "j" in i-th - level
}
}
if(i == n)
break;
char x;
cin >> x;
}
int dist[35][35];
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= inLevel[i]; ++j)
{
dist[i][j] = 10010010;
}
}
dist[0][1] = 0;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= inLevel[i]; ++j)
{
for(int k = 0; k < v[i][j].size(); ++k)
{
int pl = v[i][j][k];
if(dist[i][j] > dist[i-1][pl] + cs[i][j][pl])
{
dist[i][j] = dist[i-1][pl] + cs[i][j][pl];
}
}
}
}
int mn = 10010020;
for(int i = 1; i <= inLevel[n]; ++i)
{
mn = min(mn, dist[n][i]);
}
cout << mn;
}
sorry for my terrible english
Edited by author 11.11.2019 04:02