QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#585582#9260. Raiffeisenbank Logisticsucup-team3474#WA 3ms3824kbC++202.4kb2024-09-23 21:19:502024-09-23 21:19:51

Judging History

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

  • [2024-09-23 21:19:51]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3824kb
  • [2024-09-23 21:19:50]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10,mod=998244353;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k;
ll a[N],b[N];
char s[N];

typedef struct{
    int to,val,w;
}Node;

vector<Node> e[N];
int q[N];

vector<int> ee[N];

vector<int> mp[N];
vector<int> tf[N];

void __(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) e[i].clear(),mp[i].clear(),ee[i].clear(),tf[i].clear();
    // mp.clear();
    deque<PII> q;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w,0});
        e[v].push_back({u,w,1});
        ee[u].push_back(w);
        ee[v].push_back(w);
    }
    ee[1].push_back(-1);
    for(int i=1;i<=n;i++){
        sort(ee[i].begin(),ee[i].end());
        ee[i].erase(unique(ee[i].begin(),ee[i].end()),ee[i].end());
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=e[i].size();j++) mp[i].push_back(1e9),tf[i].push_back(0);
    }
    mp[1][0]=0;
    tf[1][0]=1;
    q.push_back({1,-1});
    while(q.size()){
        PII t=q.front();
        q.pop_front();
        int ts=lower_bound(ee[t.first].begin(),ee[t.first].end(),t.second)-ee[t.first].begin();
        
        // cout<<t.first<<" "<<t.second<<" "<<mp[t.first][t.second]<<endl;
        for(auto [to,val,w]:e[t.first]){
            if(val<=t.second) continue;
            if(w==0){
                PII tt={to,val};
                int tts=lower_bound(ee[tt.first].begin(),ee[tt.first].end(),tt.second)-ee[tt.first].begin();
                // if(mp.count(tt)) continue;
                if(!tf[tt.first][tts]){
                mp[tt.first][tts]=mp[t.first][ts];
                tf[tt.first][tts]=1;
                q.push_front(tt);
                }
            }else{
                PII tt={to,val};
                int tts=lower_bound(ee[tt.first].begin(),ee[tt.first].end(),tt.second)-ee[tt.first].begin();
                if(!tf[tt.first][tts]){
                mp[tt.first][tts]=mp[t.first][ts]+1;
                tf[tt.first][tts]=1;
                q.push_back(tt);
                }
            }
        }
    }
    int ans=1e9+8;
    for(auto v:mp[n]){
        ans=min(v,ans);
    }
    if(ans>1e8) cout<<-1<<"\n";
    else cout<<ans<<"\n";

}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _;
    cin>>_;
    while(_--){
        __();
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3572kb

input:

1
4 3
2 1 1
2 3 2
4 3 3

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3564kb

input:

2
4 3
2 1 1
2 3 2
4 3 2
8 9
1 2 5
2 3 10
4 3 15
4 5 20
5 8 25
1 6 2
6 5 30
7 6 3
8 7 4

output:

-1
1

result:

ok 2 number(s): "-1 1"

Test #3:

score: 0
Accepted
time: 2ms
memory: 3824kb

input:

8
2 1
1 2 1
2 1
2 1 1
2 1
1 1 1
2 1
2 2 1
2 1
1 2 1000000000
2 1
2 1 1000000000
2 1
1 1 1000000000
2 1
2 2 1000000000

output:

0
1
-1
-1
0
1
-1
-1

result:

ok 8 numbers

Test #4:

score: 0
Accepted
time: 2ms
memory: 3636kb

input:

1
2 1
1 2 1

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: -100
Wrong Answer
time: 3ms
memory: 3576kb

input:

1000
10 10
1 2 1
2 4 1
6 1 1
3 8 1
7 2 1
3 2 1
1 4 1
2 6 1
9 4 1
10 7 1
10 10
4 7 1
10 2 1
8 2 1
9 1 1
1 9 1
4 4 1
10 2 1
4 7 1
8 2 1
9 9 1
10 10
7 5 1
2 2 1
8 7 1
10 9 1
2 7 1
4 6 1
4 1 1
1 2 1
3 8 1
2 1 1
10 10
6 10 1
4 7 1
10 9 1
4 8 1
1 1 1
1 1 1
1 7 1
2 1 1
6 9 1
3 10 1
10 10
6 1 1
9 8 1
8 8 1
...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
0
1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
1
-1
-1
0
-1
1
-1
-1
-...

result:

wrong answer 154th numbers differ - expected: '0', found: '1'