QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#317292	#8038. Hammer to Fall	Yu_Jie	TL	7ms	8272kb	C++14	1.0kb	2024-01-28 19:44:08	2024-01-28 19:44:09

Judging History

你现在查看的是最新测评结果

[2024-01-30 14:24:05]
hack成功，自动添加数据
(/hack/528)

[2024-01-28 19:44:09]
评测

测评结果：TL
用时：7ms
内存：8272kb

查看

[2024-01-28 19:44:08]
提交

answer

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=100005,P=998244353;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,m,q,a[N],b[N],ans;
ll f[N],g[N];
vector<pair<int,int>> e[N];
int read() {
    int x=0,f=1; char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-48;
    return x*f;
}
int main() {
    n=read(); m=read(); q=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=m;i++) {
        int x=read(),y=read(),z=read();
        e[x].push_back({y,z});
        e[y].push_back({x,z});
    }
    for(int i=1;i<=q;i++) b[i]=read();
    f[b[q]]=INF;
    for(int i=q;i>=1;i--) {
        for(int j=1;j<=n;j++) g[j]=f[j];
        for(int x=1;x<=n;x++) {
            for(auto [y,z]:e[x]) {
                g[x]=min(g[x],f[y]+z);
            }
        }
        g[b[i-1]]=INF;
        for(int j=1;j<=n;j++) f[j]=g[j];
    }
    for(int i=1;i<=n;i++) ans=(ans+f[i]%P*a[i])%P;
    printf("%d\n",ans);
    return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 6932kb

input:

output:

result:

ok single line: '12'

Test #2:

score: 0

Accepted

time: 1ms

memory: 7308kb

input:

2 1 10
5000 5000
1 2 10000
1 2 2 1 2 2 1 1 1 2

output:

550000000

result:

ok single line: '550000000'

Test #3:

score: 0

Accepted

time: 1ms

memory: 7916kb

input:

10 10 10
5 14 99 14 18 4 58 39 48 60
2 4 4
6 9 56
10 8 34
7 5 96
1 3 26
3 7 92
6 8 4
5 1 72
7 6 39
7 2 93
8 8 9 10 2 2 5 9 2 3

output:

result:

ok single line: '8810'

Test #4:

score: 0

Accepted

time: 7ms

memory: 8272kb

input:

100 500 10000
89 61 65 85 89 2 32 97 13 70 29 86 68 74 84 64 54 39 26 84 56 95 73 11 70 26 60 40 84 58 68 33 65 71 55 2 11 71 49 85 14 59 38 11 60 8 81 78 27 32 52 49 35 94 62 72 64 50 12 45 77 74 92 67 92 38 81 39 12 29 60 70 53 33 25 60 7 83 4 85 47 32 13 58 85 86 44 68 44 1 81 62 97 7 66 62 5 16 ...

output:

result:

ok single line: '609241'

Test #5:

score: -100

Time Limit Exceeded

input:

100000 100000 100000
134299012 740620432 241626312 533601686 901212368 274154852 46613593 72208460 685661661 930069933 934386896 140544225 900179749 8735320 54649110 922673925 450551589 517879800 773426781 410723403 783459037 344315202 75310230 122339501 113898579 646500753 18238713 119326471 969272...