正文

图论补完计划poj3635（最短路变形）

hymscoty  hymscoty  2022-08-23  656

关键词：

Full Tank?

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 7427		Accepted: 2399

Description

After going through the receipts from your car trip through Europe this summer, you realised that the gas prices varied between the cities you visited. Maybe you could have saved some money if you were a bit more clever about where you filled your fuel?

To help other tourists (and save money yourself next time), you want to write a program for finding the cheapest way to travel between cities, filling your tank on the way. We assume that all cars use one unit of fuel per unit of distance, and start with an empty gas tank.

Input

The first line of input gives 1 ≤ n ≤ 1000 and 0 ≤ m ≤ 10000, the number of cities and roads. Then follows a line with n integers 1 ≤ p_i ≤ 100, where p_i is the fuel price in the ith city. Then follow m lines with three integers 0 ≤ u, v < n and 1 ≤ d ≤ 100, telling that there is a road between u and v with length d. Then comes a line with the number 1 ≤ q ≤ 100, giving the number of queries, and q lines with three integers 1 ≤ c ≤ 100, s and e, where c is the fuel capacity of the vehicle, s is the starting city, and e is the goal.

Output

For each query, output the price of the cheapest trip from s to e using a car with the given capacity, or "impossible" if there is no way of getting from s to e with the given car.

Sample Input

5 5
10 10 20 12 13
0 1 9
0 2 8
1 2 1
1 3 11
2 3 7
2
10 0 3
20 1 4

Sample Output

170
impossible

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int maxn=1005;
const int maxf=105;
const int inf=1e9;

typedef pair<int,int> P;

struct node{
    int f,v,t;
    bool operator <(const node&a)const{
        return a.v<v;
    }
};

int dp[maxn][maxf];
bool used[maxn][maxf];
int p[maxn];

int cap,st,ed;

vector<P> G[maxn];

void init(){
    for(int i=0;i<maxn;i++){
        for(int j=0;j<maxf;j++){
            dp[i][j]=inf;
        }
    }
    dp[st][0]=0;
    memset(used,0,sizeof(used));
}

int dij(){
    priority_queue<node> q;
    q.push((node){0,0,st});
    node tem;
    while(!q.empty()){
        node now=q.top();
        q.pop();
        int tf=now.f;
        int tv=now.v;
        int tt=now.t;
        used[tt][tf]=1;
        if(tt==ed) return tv;
        if(tf+1<=cap&&!used[tt][tf+1]&&dp[tt][tf+1]>dp[tt][tf]+p[tt]){
            dp[tt][tf+1]=dp[tt][tf]+p[tt];
            tem=(node){tf+1,dp[tt][tf+1],tt};
            q.push(tem);
        }
        for(int i=0;i<G[tt].size();i++){
            int v=G[tt][i].first;
            int w=G[tt][i].second;
            if(tf-w>=0&&!used[v][tf-w]&&dp[v][tf-w]>tv){
                dp[v][tf-w]=tv;
                tem=(node){tf-w,dp[v][tf-w],v};
                q.push(tem);
            }
        }
    }
    return -1;
}

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%d",&p[i]);
    }
    for(int i=0;i<m;i++){
        int s,t,v;
        scanf("%d %d %d",&s,&t,&v);
        G[s].push_back(P(t,v));
        G[t].push_back(P(s,v));
    }
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d %d %d",&cap,&st,&ed);
        init();
        int res=dij();
        if(res!=-1) printf("%d
",res);
        else printf("impossible
");
    }
    return 0;
}

图论补完计划poj3522（最小生成树）

SlimSpanTimeLimit:5000MS MemoryLimit:65536KTotalSubmissions:7933 Accepted:4227DescriptionGivenanundirectedweightedgraphG,youshouldfindoneofspanningtreesspecifiedasfollows.ThegraphGisanordere 查看详情

图论补完计划poj2723（2-sat）

GetLuffyOutTimeLimit:2000MS MemoryLimit:65536KTotalSubmissions:8688 Accepted:3371DescriptionRatishisayoungmanwhoalwaysdreamsofbeingahero.OnedayhisfriendLuffywascaughtbyPirateArlong.Ratishset 查看详情

变形最短路

http://poj.org/problem?id=3635 有没有感觉神似ACMER的出行计划我们知道dijkstra是贪心策略的dp嘛，贪心的是距离然而有时除了距离还有别的限制，在这里是油。这时候花费最小不一定是最优，还要考虑剩余的油dp（i，j）表示到i点时... 查看详情

poj3635fulltank?[分层图最短路]

FullTank?TimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 7248 Accepted: 2338DescriptionAftergoingthroughthereceiptsfromyourcartripthroughEuropethissummer,yourealis 查看详情

poj2253最短路变形(代码片段)

题目连接：http://poj.org/problem?id=2253DescriptionFreddyFrogissittingonastoneinthemiddleofalake.SuddenlyhenoticesFionaFrogwhoissittingonanotherstone.Heplanstovisither,butsincethewaterisdirtyandfulloftouri 查看详情

poj2253frogger——最短路变形

题目链接：http://poj.org/problem?id=2253 FroggerTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 49409 Accepted: 15729DescriptionFreddyFrogissittingonastoneinthemid 查看详情

poj-2253-frogger（最短路变形）(代码片段)

DescriptionFreddyFrogissittingonastoneinthemiddleofalake.SuddenlyhenoticesFionaFrogwhoissittingonanotherstone.Heplanstovisither,butsincethewaterisdirtyandfulloftourists‘sunscreen,hewantstoavoidswimmin 查看详情

poj1797heavytransportation（最大生成树/最短路变形）

传送门HeavyTransportationTimeLimit: 3000MS MemoryLimit: 30000KTotalSubmissions: 31882 Accepted: 8445DescriptionBackground HugoHeavyishappy.AfterthebreakdownoftheCargoli 查看详情

poj2253frogger（dijkstra变形——最短路径最小权值）

题目链接：http://poj.org/problem?id=2253DescriptionFreddyFrogissittingonastoneinthemiddleofalake.SuddenlyhenoticesFionaFrogwhoissittingonanotherstone.Heplanstovisither,butsincethewaterisdirtyandfulloftouri 查看详情

poj_2253frogger最短路变形(代码片段)

...青蛙距离，然后要求这个青蛙距离最小值。　其实就是最短路的变形，用dijkstra，原先求最短路的时候是每次确定当前最小距离的点，那么，这题只需要每次确定一个当前最有值就可以了，易证，队列后面的值是不会有更小了的... 查看详情

poj1797heavytransportation(最短路变形）(代码片段)

...最大承载量解题思路：其实这个求最大边可以近似于求最短路，只要修改下找最短路更新的条件就可以了 #include<iostream>#include<cstring>#include<cstdio>usingn 查看详情

poj-2253-frogger+最短路小变形(代码片段)

传送门：http://poj.org/problem?id=2253参考：https://www.cnblogs.com/lienus/p/4273159.html题意：给出一个无向图,求一条从1到2的路径，使得路径上的最大边权最小；思路：dij将距离更新改成取最大值即可，即dis[i]表示到达i点过程中的最大边权... 查看详情

poj-2253frogger---最短路变形&&最大边的最小值(代码片段)

题目链接：https://vjudge.net/problem/POJ-2253题目大意：青蛙A想访问青蛙B，必须跳着石头过去，不幸的是，B所在的石头太远了，需要借助其他的石头，求从A到B的路径中，青蛙最少需要的跳跃能力是多远思路：理清题意，这里规定的... 查看详情

poj2253frogger最短路变形/kruskal/a到b多条路径中的最小的最长边(代码片段)

FreddyFrogissittingonastoneinthemiddleofalake.SuddenlyhenoticesFionaFrogwhoissittingonanotherstone.Heplanstovisither,butsincethewaterisdirtyandfulloftourists‘sunscreen,hewantstoavoidswimmingandinstead 查看详情

poj-2263heavycargo---最短路变形&&最小边的最大值(代码片段)

...市b，车上的最大载重能为多少。思路：这里求的不是最短路，求的是最大容量路，意思就是每条路的最小边就是这条路的容量值，要求出最大的容量值。可以用Floyd的思想来求解。设Map[i][j]表示从i到j的容量值，递推方程变成：M... 查看详情

poj1742coin[dp补完计划](代码片段)

　　题目传送门CoinsTimeLimit: 3000MS MemoryLimit: 30000KTotalSubmissions: 41707 Accepted: 14125DescriptionPeopleinSilverlandusecoins.TheyhavecoinsofvalueA1,A2,A3...AnSilverlandd 查看详情

cf(2e)keshiinsearchofamshz(图论,最短路,建边权值变形)(代码片段)

思路: 关键是操作2的性质:随机找->找一个路径最长的点操作1,阻止建边顾名思义, 发现和最短路很想,从n到每一个点的权值嘛改变权值更新方式,边的权值为:val[i]+前面那个点是第几大的,(这里每一个出度的点都要... 查看详情

poj-2253_最短路练习(代码片段)

title:poj-2253_最短路练习date:2018-11-1711:48:51tags:acm刷题categories:ACM-最短路概述一道最短路的变形题，，虽然说解法不止这一种，，这道题看了好久都没看懂题意，，不知到在求什么，，，最后迫不得已去看了别人的思路，，理清思... 查看详情