/ Vijos / 题库 / ファーラの力 /

题解

6 条题解

  • 1
    @ 2023-08-02 11:02:15

    我写一下我对题解的理解，如果有什么不妥当的地方，还请包容和指出，谢谢！
    ans 因分为3个部分：1.中途增加光压的时间 2.中途减少光压的时间 3. 所有路程的总时间
    发现没有增加光压的话，dist是递减的，如果把每个柱子的光压下限0去掉后，光压无论在何时加都是一样的
    因为若从某刻光压小于等于0后，我们可以按需调整光压，不会出现降低光压这个操作，而不论如何最后的光压一定是h[n]
    所以

    1.光压无论在何时加都是一样的

    而我们又发现在路径上减少1个光压和在光柱上人为调整1个光压的时间是一样的
    光压差就是时间差
    我们用dist[n]表示到点n时的光压

    2.X-dist[终点]=中途减少光压的时间+所有路程的总时间

    又由1得E[终点]-dist[终点]=中途增加光压的时间

    这两个式子都是随着dist[终点]的递增而递减的
    只要算出最大的dist[终点]即可，这就是为什么要用最短路

    ans=(X-dist[终点])+(E[终点]-dist[终点)=X+E[终点]-2*dist[终点]

    # define LOCAL
# include <cstring>
# include <cstdio>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <stack>
# include <map>
# include <queue>
# include <ctime>
using namespace std;
# define REP( i, n ) for ( int i = 1; i <= n; i ++ )
# define REP_0( i, n ) for ( int i = 0; i < n; i ++ )
# define REP_0N( i, n ) for ( int i = 0; i <= n; i ++ )
# define REP_S( i, ss ) for ( char *i = ss; *i; i ++ )
# define REP_G( i, u ) for ( int i = pos[ u ]; i; i = g[ i ].frt )
# define FOR( i, a, b ) for ( int i = a; i <= b; i ++ )
# define DWN( i, a, b ) for ( int i = b; i >= a; i -- )
# define RST( a ) memset ( a, 0, sizeof ( a ) )
# define CLR( a, x ) memset ( a, x, sizeof ( a ) )
# define CPY( a, b ) memcpy ( a, b, sizeof ( a ) )
typedef long long LL;
const int inf = 1 << 30;
typedef double DB;

# define NS 101000
# define mp make_pair
# define v g[ i ].y
# define vl g[ i ].val
priority_queue < pair < LL, int > > q;
LL h[ NS ], mh[ NS ], X;
int n, m, pos[ NS ], gsz;
struct edge { int y, frt; LL val; void Set ( int yr, int fr, LL vv ) { y = yr, frt = fr, val = vv; } } g[ 601000 ];
inline void AE ( int x, int y, LL val ) { g[ ++ gsz ].Set ( y, pos[ x ], val ), pos[ x ] = gsz; }
int main ()
{
scanf ( "%d%d%lld", &n, &m, &X );
int t1, t2; LL t3;
REP ( i, n ) scanf ( "%lld", &h[ i ] ), mh[ i ] = - inf;
REP ( i, m ) scanf ( "%d%d%lld", &t1, &t2, &t3 ), AE ( t1, t2, t3 ), AE ( t2, t1, t3 );
q.push ( mp ( X, 1 ) );
while ( !q.empty () )
{
pair < LL, int > w = q.top (); q.pop ();
int u = w.second; if ( mh[ u ] != - inf ) continue;
mh[ u ] = w.first;
REP_G ( i, u ) if ( h[ u ] >= vl ) q.push ( mp ( min ( mh[ u ] - vl, h[ v ] ), v ) );
}
if ( mh[ n ] != - inf ) printf ( "%lld\n", X + h[ n ] - mh[ n ] * 2 );
else printf ( "-1\n" );
return 0;
}
  • -1
    @ 2014-10-29 17:48:12

    我写一下我对题解的理解，如果有什么不妥当的地方，还请包容和指出，谢谢！
    ans 因分为3个部分：1.中途增加光压的时间 2.中途减少光压的时间 3. 所有路程的总时间
    发现没有增加光压的话，dist是递减的，如果把每个柱子的光压下限0去掉后，光压无论在何时加都是一样的
    因为若从某刻光压小于等于0后，我们可以按需调整光压，不会出现降低光压这个操作，而不论如何最后的光压一定是h[n]
    所以

    1.光压无论在何时加都是一样的

    而我们又发现在路径上减少1个光压和在光柱上人为调整1个光压的时间是一样的
    光压差就是时间差
    我们用dist[n]表示到点n时的光压

    2.X-dist[终点]=中途减少光压的时间+所有路程的总时间

    又由1得E[终点]-dist[终点]=中途增加光压的时间

    这两个式子都是随着dist[终点]的递增而递减的
    只要算出最大的dist[终点]即可，这就是为什么要用最短路

    ans=(X-dist[终点])+(E[终点]-dist[终点)=X+E[终点]-2*dist[终点]

    • @ 2014-11-01 08:10:22

      神犇 减少光压的时间和路程总时间指什么。。
      路程总时间不就是减少光压的时间吗

  • -1
    @ 2014-10-26 19:32:47

    我终于来开坑题解了…………

    首先我们考虑X=0的情形，显然如果我们要走一条长度为T的边，就要先花费T的时间提升光压到T，然后消耗T光压走过去，因此最短路答案*2即可。

    将这个做法推广到X!=0时，我们注意到，一旦某个时刻X=0，那么做法就很好办了，因此，我们可以允许<0的高度存在，因为<0时我们可以如法炮制X=0的做法。再看标程应该就很容易理解了…………

    • @ 2014-10-28 16:47:10

      蒟蒻还是没搞明白。 大神可以再讲详细点么。。 为什么标程最后输出结果是-dist[n]*2,而不是+呢？ 我只理解了x=0的做法,如果x=0,按照您的意思不是 答案是最短路的*2+h[n] 也就是h[n]+dist[n]*2么

  • -1
    @ 2014-10-26 08:31:27

    /* Template the Final Chapter Light --- Fimbulvetr version 0.1 /
    /     In this blizzard, I will find peace. */
    # define LOCAL
    # include <cstring>
    # include <cstdio>
    # include <algorithm>
    # include <vector>
    # include <string>
    # include <set>
    # include <stack>
    # include <map>
    # include <queue>
    # include <ctime>
    using namespace std;
    # define REP( i, n ) for ( int i = 1; i <= n; i ++ )
    # define REP_0( i, n ) for ( int i = 0; i < n; i ++ )
    # define REP_0N( i, n ) for ( int i = 0; i <= n; i ++ )
    # define REP_S( i, ss ) for ( char *i = ss; *i; i ++ )
    # define REP_G( i, u ) for ( int i = pos[ u ]; i; i = g[ i ].frt )
    # define FOR( i, a, b ) for ( int i = a; i <= b; i ++ )
    # define DWN( i, a, b ) for ( int i = b; i >= a; i -- )
    # define RST( a ) memset ( a, 0, sizeof ( a ) )
    # define CLR( a, x ) memset ( a, x, sizeof ( a ) )
    # define CPY( a, b ) memcpy ( a, b, sizeof ( a ) )
    typedef long long LL;
    const int inf = 1 << 30;
    typedef double DB;

    # define NS 101000
    # define mp make_pair
    # define v g[ i ].y
    # define vl g[ i ].val
    priority_queue < pair < LL, int > > q;
    LL h[ NS ], mh[ NS ], X;
    int n, m, pos[ NS ], gsz;
    struct edge { int y, frt; LL val; void Set ( int yr, int fr, LL vv ) { y = yr, frt = fr, val = vv; } } g[ 601000 ];
    inline void AE ( int x, int y, LL val ) { g[ ++ gsz ].Set ( y, pos[ x ], val ), pos[ x ] = gsz; }
    int main ()
    {
    scanf ( "%d%d%lld", &n, &m, &X );
    int t1, t2; LL t3;
    REP ( i, n ) scanf ( "%lld", &h[ i ] ), mh[ i ] = - inf;
    REP ( i, m ) scanf ( "%d%d%lld", &t1, &t2, &t3 ), AE ( t1, t2, t3 ), AE ( t2, t1, t3 );
    q.push ( mp ( X, 1 ) );
    while ( !q.empty () )
    {
    pair < LL, int > w = q.top (); q.pop ();
    int u = w.second; if ( mh[ u ] != - inf ) continue;
    mh[ u ] = w.first;
    REP_G ( i, u ) if ( h[ u ] >= vl ) q.push ( mp ( min ( mh[ u ] - vl, h[ v ] ), v ) );
    }
    if ( mh[ n ] != - inf ) printf ( "%lld\n", X + h[ n ] - mh[ n ] * 2 );
    else printf ( "-1\n" );
    return 0;
    }

    • @ 2014-10-26 08:31:37

      这是我的程序……

    • @ 2014-10-26 13:59:31

      Orz不要光发标程求题解啊……

  • -1
    @ 2014-10-25 22:41:24

    #include<iostream>
    #include<algorithm>
    #include<queue>
    #include<string>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<ctime>
    #include<cmath>
    #include<cctype>
    using namespace std;
    int N,M,X,A,B,T,size=0;
    long long E[100001];
    long long first[100001],next[600001],v[600001],w[600001],s[100001],t[100001];
    long long x[100001];
    bool vis[100001];
    void ljb(int A,int B,int T)
    {
    size++;
    next[size]=first[A];
    first[A]=size;
    v[size]=B;
    w[size]=T;
    }
    int main()
    {
    scanf("%d%d%d",&N,&M,&X);
    for(int i=1;i<=N;i++)
    scanf("%d",&E[i]);
    for(int i=1;i<=M;i++)
    {
    scanf("%d%d%d",&A,&B,&T);
    ljb(A,B,T);
    ljb(B,A,T);
    }
    queue<int> q;
    for(int i=0;i<=N;i++)
    s[i]=1000000001;
    vis[1]=true;
    s[1]=0;
    q.push(1);
    x[1]=X;
    while(!q.empty())
    {
    int n=q.front();
    q.pop();
    int u=first[n];
    int add=0;
    while(u!=0)
    {
    if(x[n]-w[u]>E[v[u]])
    add=x[n]-w[u]-E[v[u]];
    if(w[u]+s[n]+add<s[v[u]]&&E[n]-w[u]>=0)
    {
    s[v[u]]=w[u]+s[n]+add;
    x[v[u]]=x[n]-w[u]-add;
    if(!vis[v[u]])
    {
    vis[v[u]]=true;
    q.push(v[u]);
    }
    }
    u=next[u];
    add=0;
    }
    vis[n]=false;
    }
    if(s[N]==1000000001)
    {
    printf("-1");
    return 0;
    }
    else
    {
    long long ans=2*s[N]+E[N]-X;
    cout<<ans<<endl;
    }
    return 0;
    }
    测试数据 #0: Accepted, time = 15 ms, mem = 18568 KiB, score = 1
    测试数据 #1: Accepted, time = 0 ms, mem = 18564 KiB, score = 1
    测试数据 #2: Accepted, time = 11 ms, mem = 18576 KiB, score = 1
    测试数据 #3: Accepted, time = 0 ms, mem = 18572 KiB, score = 1
    测试数据 #4: Accepted, time = 15 ms, mem = 18576 KiB, score = 1
    测试数据 #5: Accepted, time = 0 ms, mem = 18572 KiB, score = 1
    测试数据 #6: Accepted, time = 0 ms, mem = 18572 KiB, score = 1
    测试数据 #7: Accepted, time = 0 ms, mem = 18564 KiB, score = 1
    测试数据 #8: Accepted, time = 0 ms, mem = 18572 KiB, score = 1
    测试数据 #9: Accepted, time = 15 ms, mem = 18568 KiB, score = 1
    测试数据 #10: Accepted, time = 0 ms, mem = 18564 KiB, score = 1
    测试数据 #11: Accepted, time = 0 ms, mem = 18568 KiB, score = 1
    测试数据 #12: Accepted, time = 0 ms, mem = 18572 KiB, score = 1
    测试数据 #13: Accepted, time = 15 ms, mem = 18572 KiB, score = 1
    测试数据 #14: Accepted, time = 0 ms, mem = 18568 KiB, score = 1
    测试数据 #15: Accepted, time = 0 ms, mem = 18564 KiB, score = 1
    测试数据 #16: Accepted, time = 0 ms, mem = 18572 KiB, score = 1
    测试数据 #17: Accepted, time = 0 ms, mem = 18568 KiB, score = 1
    测试数据 #18: Accepted, time = 0 ms, mem = 18572 KiB, score = 1
    测试数据 #19: Accepted, time = 15 ms, mem = 18572 KiB, score = 1
    测试数据 #20: Accepted, time = 280 ms, mem = 18600 KiB, score = 2
    测试数据 #21: Accepted, time = 390 ms, mem = 18632 KiB, score = 2
    测试数据 #22: Accepted, time = 358 ms, mem = 18700 KiB, score = 2
    测试数据 #23: Accepted, time = 421 ms, mem = 18720 KiB, score = 2
    测试数据 #24: Accepted, time = 436 ms, mem = 18624 KiB, score = 2
    测试数据 #25: Accepted, time = 15 ms, mem = 18572 KiB, score = 2
    测试数据 #26: Accepted, time = 171 ms, mem = 18572 KiB, score = 2
    测试数据 #27: Accepted, time = 390 ms, mem = 18780 KiB, score = 2
    测试数据 #28: Accepted, time = 234 ms, mem = 18572 KiB, score = 2
    测试数据 #29: Accepted, time = 124 ms, mem = 18572 KiB, score = 2
    测试数据 #30: Accepted, time = 31 ms, mem = 18588 KiB, score = 2
    测试数据 #31: Accepted, time = 234 ms, mem = 18624 KiB, score = 2
    测试数据 #32: Accepted, time = 78 ms, mem = 18568 KiB, score = 2
    测试数据 #33: Accepted, time = 171 ms, mem = 18568 KiB, score = 2
    测试数据 #34: WrongAnswer, time = 0 ms, mem = 18568 KiB, score = 0
    测试数据 #35: Accepted, time = 312 ms, mem = 18632 KiB, score = 2
    测试数据 #36: WrongAnswer, time = 15 ms, mem = 18568 KiB, score = 0
    测试数据 #37: WrongAnswer, time = 15 ms, mem = 18568 KiB, score = 0
    测试数据 #38: Accepted, time = 62 ms, mem = 18576 KiB, score = 2
    测试数据 #39: Accepted, time = 31 ms, mem = 18572 KiB, score = 2
    测试数据 #40: Accepted, time = 156 ms, mem = 18564 KiB, score = 2
    测试数据 #41: Accepted, time = 46 ms, mem = 18568 KiB, score = 2
    测试数据 #42: Accepted, time = 140 ms, mem = 18568 KiB, score = 2
    测试数据 #43: Accepted, time = 109 ms, mem = 18676 KiB, score = 2
    测试数据 #44: Accepted, time = 265 ms, mem = 18660 KiB, score = 2
    测试数据 #45: Accepted, time = 31 ms, mem = 18572 KiB, score = 2
    测试数据 #46: Accepted, time = 468 ms, mem = 18796 KiB, score = 2
    测试数据 #47: Accepted, time = 280 ms, mem = 18780 KiB, score = 2
    测试数据 #48: Accepted, time = 249 ms, mem = 18772 KiB, score = 2
    测试数据 #49: Accepted, time = 358 ms, mem = 18708 KiB, score = 2
    测试数据 #50: WrongAnswer, time = 31 ms, mem = 18568 KiB, score = 0
    测试数据 #51: WrongAnswer, time = 171 ms, mem = 18568 KiB, score = 0
    测试数据 #52: Accepted, time = 171 ms, mem = 18568 KiB, score = 2
    测试数据 #53: WrongAnswer, time = 156 ms, mem = 18572 KiB, score = 0
    测试数据 #54: WrongAnswer, time = 156 ms, mem = 18568 KiB, score = 0
    测试数据 #55: Accepted, time = 343 ms, mem = 18784 KiB, score = 2
    测试数据 #56: WrongAnswer, time = 46 ms, mem = 18568 KiB, score = 0
    测试数据 #57: WrongAnswer, time = 0 ms, mem = 18568 KiB, score = 0
    测试数据 #58: Accepted, time = 187 ms, mem = 18568 KiB, score = 2
    测试数据 #59: WrongAnswer, time = 62 ms, mem = 18572 KiB, score = 0
    WrongAnswer, time = 7279 ms, mem = 18796 KiB, score = 80
    蒟蒻求助

  • -2
    @ 2014-10-26 08:32:58

    #include<cstdio>
    #include<queue>
    #include<vector>
    #include<algorithm>
    using namespace std;
    const int MAXN = 100005;
    const long long INF = 100001000010000100ll; // >> 10^9*10^5

    int H[MAXN];
    long long dist[MAXN];
    vector<int> to[MAXN], cost[MAXN];

    struct Dat{
    long long d;
    int v;
    Dat(long long d, int v):d(d),v(v){}
    bool operator<(const Dat& a)const{ return d < a.d;}
    };

    int main(){
    int N, M, X, A, B, T;
    scanf("%d%d%d",&N,&M,&X);

    for(int i = 1; i <= N; i++) scanf("%d",&H[i]);
    for(int i = 0; i < M; i++){
    scanf("%d%d%d",&A,&B,&T);
    to[A].push_back(B);
    cost[A].push_back(T);
    to[B].push_back(A);
    cost[B].push_back(T);
    }

    for(int i = 1; i <= N; i++) dist[i] = -INF;

    priority_queue<Dat> q;
    q.push(Dat(X,1));

    while(!q.empty()){
    Dat now = q.top(); q.pop();
    if(dist[now.v] != -INF) continue;
    dist[now.v] = now.d;
    for(int i = 0; i < to[now.v].size(); i++){
    int u = to[now.v][i], c = cost[now.v][i];
    if(c > H[now.v]) continue;
    q.push(Dat(min(now.d-c, (long long)H[u]), u));
    }
    }

    if(dist[N] == -INF) puts("-1");
    else printf("%lld\n",X+H[N]-dist[N]*2);

    return 0;
    }

    • @ 2014-10-26 08:33:06

      这是JOI标程……

    • @ 2014-10-30 19:43:58

      这个标程...
      Orz...

  • 1

ファーラの力

信息

ID
1880
难度
8
分类
(无)
标签
(无)
递交数
370
已通过
46
通过率
12%
被复制
3
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1