提交记录 11373


用户 题目 状态 得分 用时 内存 语言 代码长度
hxb noi19a. 【NOI2019】回家路线 Accepted 100 169.857 ms 89884 KB C++ 1.68 KB
提交时间 评测时间
2019-12-16 20:37:48 2020-08-01 02:42:47
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int from;
    int to;
    int from_time;
    int to_time;
    node()
    {
    }
    node(int _a,int _b,int _c,int _d)
    {
        from=_a,to=_b,from_time=_c,to_time=_d;
    }
}q[200005];
bool cmp(node x,node y)
{
    if (x.from_time==y.from_time) return x.to_time<y.to_time;
    return x.from_time<y.from_time;
}
int read()
{
    int x=0;
    bool f=0;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')f=1;
        c=getchar();
    }
    while(isdigit(c))
    {
        x=x*10+c-'0';
        c=getchar();
    }
    if(f)x=-x;
    return x;
}
long long n,m,A,B,C,vis[100005][55],sum[100005][55],cnt[100005];
long long ans=1e18;
int main() {
    //freopen("route.in","r",stdin);
    //freopen("route.out","w",stdout);
    memset(vis,0x7fffffffffffffff,sizeof(vis));
    memset(sum,0x7fffffffffffffff,sizeof(sum));
    vis[1][1]=0;
    sum[1][1]=0;
    cnt[1]=1;
    cin>>n>>m>>A>>B>>C;
    for (int i=0;i<m;i++)
    {
        int a=read(),b=read(),c=read(),d=read();
        q[i]=node(a,b,c,d);
    }
    sort(q,q+m,cmp);
    for (int i=0;i<m;i++)
    {
        long long minn=0x7fffffffffffffff;
        for (int j=1;j<=cnt[q[i].from];j++)
        {
            if (vis[q[i].from][j]>q[i].from_time) continue;
            int y=q[i].from_time-vis[q[i].from][j];
            minn=min(minn,(long long)sum[q[i].from][j]+(long long)A*y*y+(long long)B*y+C);
        }
        if (minn!=(long long)0x7fffffffffffffff)
        {
            sum[q[i].to][++cnt[q[i].to]]=minn;
            vis[q[i].to][cnt[q[i].to]]=q[i].to_time;
        }
    }
    for (int i=1;i<=cnt[n];i++)ans=min(ans,sum[n][i]+vis[n][i]);
    cout<<ans<<endl;
    return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #16.988 ms83 MB + 996 KBAcceptedScore: 5

Testcase #27.025 ms83 MB + 996 KBAcceptedScore: 5

Testcase #37.031 ms83 MB + 996 KBAcceptedScore: 5

Testcase #46.987 ms83 MB + 996 KBAcceptedScore: 5

Testcase #57.461 ms84 MB + 48 KBAcceptedScore: 5

Testcase #67.474 ms84 MB + 48 KBAcceptedScore: 5

Testcase #77.477 ms84 MB + 48 KBAcceptedScore: 5

Testcase #87.486 ms84 MB + 48 KBAcceptedScore: 5

Testcase #97.47 ms84 MB + 48 KBAcceptedScore: 5

Testcase #107.44 ms84 MB + 48 KBAcceptedScore: 5

Testcase #118.256 ms84 MB + 48 KBAcceptedScore: 5

Testcase #127.479 ms84 MB + 48 KBAcceptedScore: 5

Testcase #138.272 ms84 MB + 48 KBAcceptedScore: 5

Testcase #147.5 ms84 MB + 48 KBAcceptedScore: 5

Testcase #1563.272 ms87 MB + 796 KBAcceptedScore: 5

Testcase #1655.31 ms87 MB + 796 KBAcceptedScore: 5

Testcase #1741.052 ms87 MB + 796 KBAcceptedScore: 5

Testcase #1837.151 ms87 MB + 796 KBAcceptedScore: 5

Testcase #19169.857 ms87 MB + 796 KBAcceptedScore: 5

Testcase #2038.062 ms87 MB + 796 KBAcceptedScore: 5


Judge Duck Online | 评测鸭在线
Server Time: 2024-10-05 10:46:40 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用