VO17PHD – spoj

Đề bài

Thuật toán

  • (đang cập nhập)

Code

#include <bits/stdc++.h>
using namespace std;
#define FORE(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = a; i >= b; --i)
#define FOR(i,a,b) for(int i = a; i < b; ++i)
#define pb push_back
#define endl '\n'
#define ll long long
#define X first
#define Y second
 
const int MAXN = 1e5 * 5;
const int base = 1e9 + 7;
const int N = 5000;
typedef pair<ll,ll> ii;
typedef pair<ii,int> iii;
 
int n,m;
int p[MAXN];
ll d[MAXN],f[MAXN];
priority_queue<iii> h;
vector<int> a[MAXN],c[MAXN];
 
void dijkstra()
{
    FORE(i,1,n) d[i] = 1e15;
    FORE(i,1,n) f[i] = 0;
    d[1] = 0;
    f[1] = p[1];
    h.push(iii(ii(0,p[1]),1));
    while(h.size())
    {
        int u = h.top().Y;
        ll du = -h.top().X.X;
        ll fu = h.top().X.Y;
        h.pop();
        if (du != d[u] || f[u] != fu) continue;
        for(int i = 0; int v = a[u][i]; ++i)
        if (d[v] > d[u] + c[u][i])
        {
            d[v] = d[u] + c[u][i];
            f[v] = f[u] + p[v];
            h.push(iii(ii(-d[v],f[v]),v));
        }
        else
        if (d[v] == d[u] + c[u][i] && f[v] < f[u] + p[v])
        {
            f[v] = f[u] + p[v];
            h.push(iii(ii(-d[v],f[v]),v));
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("vo17phd.inp" , "r" , stdin);
    //("vo17phd.out" , "w" , stdout);
    cin>>n;
    FORE(i,1,n) cin>>p[i];
    cin>>m;
    FORE(i,1,m)
    {
        int u,v,w;
        cin>>u>>v>>w;
        a[u].pb(v); c[u].pb(w);
        a[v].pb(u); c[v].pb(w);
    }
    FORE(i,1,n) a[i].pb(0);
    dijkstra();
    if (d[n] == 1e15) cout<<"impossible"<<endl;
    else cout<<d[n]<<' '<<f[n]<<endl;
    return 0;
}
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*