NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #213407 | #2058. 小游戏 | lina | 70 | 72ms | 5548kb | C++11 | 4.6kb | 2024-11-11 21:39:23 | 2024-11-11 23:07:45 |
answer
#include <bits/stdc++.h>
//#define int long long
#define file(x) {freopen(x".in", "r", stdin); freopen(x".out", "w", stdout);}
namespace Fastio{struct Reader{template<typename T>Reader&operator>>(T&x){x=0;short f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();x*=f;return*this;}Reader&operator>>(double&x){x=0;double t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(long double&x){x=0;long double t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(__float128&x){x=0;__float128 t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(char&c){c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();return*this;}Reader&operator>>(char*str){int len=0;char c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();while(c!=' '&&c!='\n'&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return*this;}Reader&operator>>(std::string&str){str.clear();char c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();while(c!=' '&&c!='\n'&&c!='\r')str.push_back(c),c=getchar();return*this;}Reader(){}}cin;const char endl='\n';struct Writer{const int Setprecision=6;typedef int mxdouble;template<typename T>Writer&operator<<(T x){if(x==0){putchar('0');return*this;}if(x<0)putchar('-'),x=-x;static short sta[40];short top=0;while(x>0)sta[++top]=x%10,x/=10;while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(long double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(long double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(__float128 x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(__float128)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(char c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(std::string str){int st=0,ed=str.size();while(st<ed)putchar(str[st++]);return*this;}Writer(){}}cout;}using namespace Fastio;
#define io Fastio::cin
#define IO Fastio::cout
int T = 1;
const int A(1e3+5);
int dp[A][A],hp[A],n,e,m;
std::queue<std::pair<int,int>> q;
std::vector<std::pair<int,int>> g[A];
int bfs(){
int u,d,v,z,nd;
memset(dp,0x3f,sizeof(dp));
dp[1][m]=0;
q.push(std::make_pair(1,m));
for(;q.size();){
u=q.front().first;
d=q.front().second;
q.pop();
for(auto& i:g[u]){
v=i.first;
z=i.second;
if(z>=d){
continue;
}
nd=std::min(m,d-z+hp[v]);
if(dp[v][nd]==0x3f3f3f3f){
dp[v][nd]=dp[u][d]+1;
q.push(std::make_pair(v,nd));
}
}
}
d=*std::min_element(dp[n]+1,dp[n]+m+1);
return d==0x3f3f3f3f?-1:d;
}
void solve(){
std::cin>>n>>e>>m;
for(int i=1;i<=n;i++){
std::cin>>hp[i];
}
for(int i=1,u,v,w;i<=e;i++){
std::cin>>u>>v>>w;
g[u].push_back(std::make_pair(v,w));
g[v].push_back(std::make_pair(u,w));
}
std::cout<<bfs()<<'\n';
}
int32_t main(){
// file("A");
// Fastio::cin >> T;
while(T--){
solve();
}
return 0;
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 5216kb
input:
5 10 10 3 3 0 1 1 4 4 1 4 3 1 3 2 6 3 4 10 5 1 5 1 3 9 2 5 19 2 5 1 5 2 10 2 1 4
output:
1
result:
ok single line: '1'
Test #2:
score: 10
Accepted
time: 0ms
memory: 5212kb
input:
5 10 10 1 0 1 3 0 5 2 1 5 2 8 4 3 18 1 3 10 5 3 5 2 3 8 5 3 15 3 1 11 4 5 9 2 4 1
output:
-1
result:
ok single line: '-1'
Test #3:
score: 10
Accepted
time: 4ms
memory: 5212kb
input:
5 10 10 0 3 1 1 1 1 3 12 5 4 8 1 1 6 5 2 1 2 5 3 1 4 2 1 4 4 4 5 5 4 2 9 3 4 2
output:
2
result:
ok single line: '2'
Test #4:
score: 10
Accepted
time: 0ms
memory: 5216kb
input:
20 50 20 4 0 3 4 3 0 5 2 5 0 5 2 5 2 0 6 2 3 4 2 16 5 18 9 1 24 14 16 27 5 16 32 14 7 31 13 20 23 6 ...
output:
10
result:
ok single line: '10'
Test #5:
score: 10
Accepted
time: 4ms
memory: 5248kb
input:
100 500 20 2 5 5 3 0 1 1 3 4 2 5 5 5 4 5 3 1 0 2 5 5 5 2 2 1 4 0 1 6 0 1 5 2 4 5 4 4 6 3 0 0 1 5 1 3...
output:
11
result:
ok single line: '11'
Test #6:
score: 10
Accepted
time: 13ms
memory: 5480kb
input:
500 1000 500 143 113 118 133 51 100 155 76 81 43 8 91 85 65 61 69 1 30 135 125 0 43 126 20 40 52 165...
output:
11
result:
ok single line: '11'
Test #7:
score: 10
Accepted
time: 51ms
memory: 5548kb
input:
1000 5000 1000 94 154 195 48 124 134 103 168 192 122 101 8 5 197 62 123 36 129 90 48 24 43 104 7 108...
output:
32
result:
ok single line: '32'
Test #8:
score: 0
Runtime Error
input:
10000 50000 10000 30 96 44 6 84 58 47 34 35 80 49 45 47 76 93 16 2 83 23 79 81 12 66 81 96 3 37 4 69...
output:
result:
Test #9:
score: 0
Runtime Error
input:
30000 100000 20000 21 95 28 93 22 5 16 70 27 36 38 21 7 11 8 46 88 19 98 80 70 53 73 83 79 93 55 75 ...
output:
result:
Test #10:
score: 0
Runtime Error
input:
30000 100000 20000 94 72 1 42 14 15 63 14 26 25 44 9 1 71 75 85 98 80 87 49 10 47 73 16 98 13 62 72 ...
