题目链接：

http://codeforces.com/problemset/problem/301/B

B. Yaroslav and Time

time limit per test2 seconds
memory limit per test256 megabytes
#### 问题描述
> Yaroslav is playing a game called "Time". The game has a timer showing the lifespan he's got left. As soon as the timer shows 0, Yaroslav's character dies and the game ends. Also, the game has n clock stations, station number i is at point (xi, yi) of the plane. As the player visits station number i, he increases the current time on his timer by ai. The stations are for one-time use only, so if the player visits some station another time, the time on his timer won't grow.
>
> A player spends d·dist time units to move between stations, where dist is the distance the player has covered and d is some constant. The distance between stations i and j is determined as |xi - xj| + |yi - yj|.
>
> Initially, the player is at station number 1, and the player has strictly more than zero and strictly less than one units of time. At station number 1 one unit of money can increase the time on the timer by one time unit (you can buy only integer number of time units).
>
> Now Yaroslav is wondering, how much money he needs to get to station n. Help Yaroslav. Consider the time to buy and to increase the timer value negligibly small.
#### 输入
> The first line contains integers n and d (3 ≤ n ≤ 100, 103 ≤ d ≤ 105) — the number of stations and the constant from the statement.
>
> The second line contains n - 2 integers: a2, a3, ..., an - 1 (1 ≤ ai ≤ 103). The next n lines contain the coordinates of the stations. The i-th of them contains two integers xi, yi (-100 ≤ xi, yi ≤ 100).
>
> It is guaranteed that no two stations are located at the same point.
#### 输出
> In a single line print an integer — the answer to the problem.
####样例输入
> 3 1000
> 1000
> 0 0
> 0 1
> 0 3

样例输出

2000

题意

给你二维上的n个点，两个点的时间消耗为哈密顿距离*d，且到第i个点能补充a[i]的时间，问你在起始点需要买多少的时间才能保证你能够到终点。

题解

对于每条边（u,v)，边权定为d*(u到v的哈密顿距离）-a[v]，然后由点n到点1跑spfa最短路，这里注意：由于题目给的d和a的范围，导致都是正权图。

代码

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<ctime>

#include<vector>

#include<cstdio>

#include<string>

#include<bitset>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<functional>

using namespace std;

#define X first

#define Y second

#define mkp make_pair

#define lson (o<<1)

#define rson ((o<<1)|1)

#define mid (l+(r-l)/2)

#define sz() size()

#define pb(v) push_back(v)

#define all(o) (o).begin(),(o).end()

#define clr(a,v) memset(a,v,sizeof(a))

#define bug(a) cout<<#a<<" = "<<a<<endl

#define rep(i,a,b) for(int i=a;i<(b);i++)

#define scf scanf

#define prf printf

typedef __int64 LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;

const LL INFL=0x3f3f3f3f3f3f3f3fLL;

const double eps=1e-8;

const double PI = acos(-1.0);

//start----------------------------------------------------------------------

const int maxn=111;

struct Edge {

    int u,v,d;

    Edge(int u,int v,int d):u(u),v(v),d(d) {}

};

int n,D;

int arr[maxn];

int mat[maxn][maxn];

PII pt[maxn];

int dis(int i,int j) {

    return abs(pt[i].X-pt[j].X)+abs(pt[i].Y-pt[j].Y);

}

bool inq[maxn];

LL d[maxn];

LL spfa(int s) {

    queue<int> Q;

    clr(inq,0);

    for(int i=1; i<=n; i++) d[i]=INFL;

    d[s]=0,inq[s]=true,Q.push(s);

    while(!Q.empty()) {

        int u=Q.front();

        Q.pop();

        inq[u]=false;

        for(int v=1;v<=n;v++){

            if(v==u) continue;

            if(d[v]>d[u]+mat[u][v]){

                d[v]=d[u]+mat[u][v];

                if(!inq[v]){

                    Q.push(v); inq[v]=1;

                }

            }

        }

    }

    return d[1];

}

int main() {

    scf("%d%d",&n,&D);

    arr[1]=arr[n]=0;

    for(int i=2; i<n;i++) scf("%d",&arr[i]);

    for(int i=1; i<=n; i++) {

        scf("%d%d",&pt[i].X,&pt[i].Y);

    }

    for(int i=1; i<=n; i++) {

        for(int j=1; j<=n; j++) {

            if(i==j) mat[i][j]=0;

            else mat[i][j]=dis(i,j)*D-arr[j];

        }

    }

    LL ans=spfa(n);

    prf("%I64d\n",ans);

    return 0;

}

//end-----------------------------------------------------------------------

巴特西

Codeforces Round #182 (Div. 1) B. Yaroslav and Time 最短路

题目链接：

B. Yaroslav and Time

样例输出

题意

题解

代码

最新文章

热门文章