1. 首页
2. 最短路
3. 本页

Codeforces 96D Volleyball (shortest paths)

题意：~

思路：先处理出乘坐出租车能到达的点，建图跑最短路即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int MAXN = 100010;
const LL INF = 1e18 + 7;
const int lowINF = 0x3f3f3f3f;
struct Edge
{
    int v;
    LL cost;
    Edge(int _v = 0, LL _cost = 0): v(_v), cost(_cost) {}
};
vector<Edge>E[MAXN];
vector<Edge>G[MAXN];
void addedge(int u, int v, LL w)
{
    E[u].push_back(Edge(v, w));
}

void addeg(int u, int v, LL w)
{
    G[u].push_back(Edge(v, w));
}

bool vis[MAXN];
int cnt[MAXN];
LL dist[MAXN];
bool SPFA(int start, int n)
{
    memset(vis, false, sizeof(vis));
    for(int i = 1; i <= n; i++)dist[i] = INF;
    vis[start] = true;
    dist[start] = 0;
    queue<int>que;
    while(!que.empty())que.pop();
    que.push(start);
    memset(cnt, 0, sizeof(cnt));
    cnt[start] = 1;
    while(!que.empty())
    {
        int u = que.front();
        que.pop();
        vis[u] = false;
        for(int i = 0; i < E[u].size(); i++)
        {
            int v = E[u][i].v;
            if(dist[v] > dist[u] + E[u][i].cost)
            {
                dist[v] = dist[u] + E[u][i].cost;
                if(!vis[v])
                {
                    vis[v] = true;
                    que.push(v);
                    if(++cnt[v] > n)return false;
                }
            }
        }
    }
    return true;
}

bool mk[1050];
//cost len st u
void fd(LL cost, LL len, int st, int u)
{
    if(!len) return;
    for(LL i = 0; i < G[u].size(); i++)
    {
        LL v = G[u][i].v;
        LL w = G[u][i].cost;
        if(w <= len && !mk[v])
        {
            addedge(st, v, cost);
            mk[v] = 1;
            fd(cost, len - w, st, v);
        }
    }
}

map<int, map<int, int > >mp;
int gg[1010][1010];

int main()
{
    int n, m;
    cin >> n >> m;
    int st, ed;
    cin >> st >> ed;
    int u, v, w;
    memset(gg, lowINF, sizeof(gg));
    for(int i = 0; i < m; ++i)
    {
        scanf("%d%d%d", &u, &v, &w);
        if(w < gg[u][v])
        {
            gg[u][v] = w;
            gg[v][u] = w;
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = i + 1; j <= n; ++j)
        {
            if(gg[i][j] != lowINF)
            {
                addeg(i, j, gg[i][j]);
                addeg(j, i, gg[i][j]);
            }
        }
    }
    int x, c;
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d%d", &x, &c);
        memset(mk, 0, sizeof(mk));
        mk[i] = 1;
        fd(c, x, i, i);
    }
    SPFA(st, n);
    if(dist[ed] == INF) cout << "-1" << endl;
    else cout << dist[ed] << endl;
    return 0;
}