sgu-240 Runaway

题目大意:

给你一张无向图,点数为N(N<=100),边数为M(M<=10000),起点为S,终点为一个集合End,且|End|=E,然后对于每条边,有5个参数,Ai,Bi,Ti,Ri,Pi,分别表示边i连在Ai,Bi间,假设你到边i的一端的时候已经走过的距离为D,那么你到达另一端的时间为Ri+(D+Ti)?Pi,令F[i]表示从S走到i的任意一条路径上走过的所有边中走过每条边所花费的时间的最大值最小是多少。我们令ans=min(F[i](i∈End)),如果ans<=H,则输出YES,并且输出ans,然后输出路径上的点数和路径上包含了那些点。

解题思路:

观察后我们可以发现,答案可以二分,那么我们就二分ans。

然后我们就只需要知道当ans=now时,我们只经过那些通过时间不超过now的边是否能够到达集合End中的一个点。

然后我们分析一下发现,如果我们在已经花费了T1时间到达a点,显然比在已经花费了T2时间到达a点要更有可能到达集合End,所以我们只需要SPFA最短路就行了。时间复杂度O(KE)。

AC代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>

using namespace std;

int N,M,H,S,EN;
struct bian_
{
    int aim;
    int next;
    int T;
    int R;
    int P;
}bian[20010]={{0,0,0,0,0}};

int First[110]={0};

int ans=2e9;
int ansp=0;
int fa[110]={0};
int Out[110]={0};
int dist[110]={0};
int dui[810]={0};
int duip=0;
int hash[110]={0};
int E[110]={0};

void Add(int a,int b,int t,int r,int p,int k)
{
    bian[k].next=First[a];
    bian[k].aim=b;
    bian[k].T=t;
    bian[k].R=r;
    bian[k].P=p;
    First[a]=k;
    return;
}

bool check(int Max)
{
    memset(dist,-1,sizeof(dist));
    duip=0;
    dist[S]=0;
    dui[++duip]=S;
    for(int i=1;i<=duip;i++)
    {
        int u=dui[i];
        for(int p=First[u];p!=0;p=bian[p].next)
        {
            int TT=dist[u]+bian[p].T;
            int v=bian[p].aim;
            if(dist[v]==-1) dist[v]=2147483647;
            if((long long)TT*bian[p].P+bian[p].R<=(long long)Max && TT<dist[v])
            {
                fa[v]=u;
                dist[v]=TT;
                if(hash[v]==0)
                {
                    hash[v]=1;
                    dui[++duip]=v;
                }
            }
        }
        hash[u]=0;
    }
    for(int i=1;i<=EN;i++)
    {
        if(dist[E[i]]!=2147483647 && dist[E[i]]!=-1)
        {
            ansp=0;
            for(int j=E[i];j!=S;j=fa[j])
                Out[++ansp]=j;
            return true;
        }
    }
    return false;
}

int main()
{
    freopen("sgu240.in","r",stdin);
    freopen("sgu240.out","w",stdout);
    scanf("%d%d%d%d%d",&N,&M,&H,&S,&EN);
    for(int i=1;i<=M;i++)
    {
        int a,b,t,r,p;
        scanf("%d%d%d%d%d",&a,&b,&t,&r,&p);
        Add(a,b,t,r,p,(i<<1)-1);
        Add(b,a,t,r,p,i<<1);
    }
    for(int i=1;i<=EN;i++)
        scanf("%d",&E[i]);
    for(int L=0,R=H;L<=R;)
    {
        int mid=(L+R)>>1;
        if(check(mid)==true)
        {
            ans=mid;
            R=mid-1;
        }
        else L=mid+1;
    }
    if(ans==2e9)
        cout<<"NO"<<endl;
    else
    {
        cout<<"YES"<<endl;
        cout<<ans<<endl;
        cout<<ansp+1<<‘ ‘<<S;
        for(int i=ansp;i>=1;i--)
            printf(" %d",Out[i]);
        cout<<endl;
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}
时间: 05-09

sgu-240 Runaway的相关文章

【SGU 390】Tickets (数位DP)

Tickets Description Conductor is quite a boring profession, as all you have to do is just to sell tickets to the passengers. So no wonder that once upon a time in a faraway galaxy one conductor decided to diversify this occupation. Now this conductor

ACM: SGU 101 Domino- 欧拉回路-并查集

sgu 101 - Domino Time Limit:250MS     Memory Limit:4096KB     64bit IO Format:%I64d & %I64u Description Dominoes – game played with small, rectangular blocks of wood or other material, each identified by a number of dots, or pips, on its face. The bl

SGU 116 Index of super-prime 数论+完全背包+输出方案

题目链接:http://acm.sgu.ru/problem.php?contest=0&problem=116 题意好晦涩 给你一个不超过一万的数 问它最少可以用多少个“超级素数”来表示 使“超级素数”之和等于它 如果无法这样表示 输出0 否则 按非降序形式输出方案 数论部分就模板的问题 没什么说的 完全背包方面也很常规 说说[输出方案] 背包九讲的伪码给的是二维dp[]的方法 实际上稍加改动就可以用在一维数组上 用一个rec[]记录dp[]的当前状态是从哪个状态转移而来(即上一个状态) 通过

SGU 乱搞日志

SGU 100 A+B :太神不会 SGU 101 Domino: 题目大意:有N张骨牌,两张骨牌有两面有0到6的数字,能相连当且仅当前后数字相同,问能否有将N张骨牌连接的方案?思路:裸的欧拉回路,注意自环,连通 1 //sgu101 2 #include<iostream> 3 #include<cstdio> 4 #include <math.h> 5 #include<algorithm> 6 #include<string.h> 7 #i

SGU 275 To xor or not to xor (高斯消元)

题目地址:SGU 275 首先,贪心的思想,每一二进制位上要尽量是1,而能不能是1用高斯消元来解决.当该位有一个可以使之为1的变元时,就说明这位可以为1,而且令该变元控制该位,然后向低位消元. 代码如下: #include <iostream> #include <string.h> #include <math.h> #include <queue> #include <algorithm> #include <stdlib.h>

SGU 221.Big Bishops(DP)

题意: 给一个n*n(n<=50)的棋盘,放上k个主教(斜走),求能放置的种类总数. Solution : 同SGU 220,加个高精度就好了. code #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> using namespace std; string f[2][250][250], ans;

SGU 193.Chinese Girls&#39; Amusement

/* 实际上就是求一个k,满足k<=n/2,且gcd(n,k)=1 如果n为奇数,k为[n/2] 如果n为偶数,k=n/2-1-(n/2)%2 */ #include <iostream> using namespace std; string s; void div2() { string t; int l = s.size() - 1, tem = s[0] - '0'; if (tem > 1) t += '0' + tem / 2; tem &= 1; for (i

sgu 495 Kids and Prizes

计算出每个人得到礼物的概率,然后加起来即可 1 #include<iostream> 2 #include<string.h> 3 #include<algorithm> 4 #include<stdio.h> 5 using namespace std; 6 double dp[101010]; 7 int main(){ 8 int n,m; 9 while(cin>>n>>m){ 10 dp[1]=1; 11 for(int i

SGU 112 a^b-b^a

JAVA大数.... a^b-b^a Time Limit: 250MS   Memory Limit: 4096KB   64bit IO Format: %I64d & %I64u [Submit]   [Go Back]   [Status] Description You are given natural numbers a and b. Find ab-ba. Input Input contains numbers a and b (1≤a,b≤100). Output Write

【容斥+大数】SGU 476 Coach&#39;s Trouble

通道 题意:有3*n个人,分成n组,每组三个人.给出k个三元组,这三个人不可组队,问最后可以组队的总方案数 思路: 当k=0时,有(C[3*n][3]*C[3*n-3][3]*……*C[3][3])/n!种方案,展开以后可以得到dp[n]=(3*n)!/n!/6^n. 显然可以写成递推式:dp[n]=dp[n-1]*(3*n-1)*(3*n-2)/2. 那么容斥一下,答案=总方案数-至少含一个禁止组合的+至少含两个禁止组合的-…… 二进制暴力TLE了.DFS的话会有很多剪枝,当前几个已经出现冲突