QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#690717 | #9431. The Quest for El Dorado | Evan | WA | 98ms | 5616kb | C++20 | 2.6kb | 2024-10-31 01:07:48 | 2024-10-31 01:07:50 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define tp tuple<int,int,int>
bool cmp(const pair<int,int>& a,const pair<int,int>& b)
{
if(a.first!=b.first){return a.first<b.first;}
else{return a.second<b.second;}
}
void solve()
{
int n,m,k;
int i,j,u,v,c,l,r;
scanf("%d %d %d",&n,&m,&k);
vector<tp> s[n+10];
for(i=1;i<=m;i++)
{
scanf("%d %d %d %d",&u,&v,&c,&l);
s[u].push_back({v,c,l});
s[v].push_back({u,c,l});
}
vector<pair<int,int>> t(k+10);
vector<pair<int,int>> st[m+10];
vector<int> vis(n+10);
for(i=1;i<=k;i++)
{
scanf("%d %d",&u,&v);
t[i]={u,v};
st[u].push_back({v,i});
}
for(i=1;i<=m;i++)
{
sort(st[i].begin(),st[i].end());
}
priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>> pq;
pq.push({1,0,1});
while(!pq.empty())
{
tp o=pq.top();pq.pop();
int x=get<0>(o),y=get<1>(o),z=get<2>(o);
if(vis[z]){continue;}
vis[z]=1;
for(i=0;i<s[z].size();i++)
{
if(vis[get<0>(s[z][i])]){continue;}
int xx=get<0>(s[z][i]),yy=get<1>(s[z][i]),zz=get<2>(s[z][i]);
if(t[x].first==yy&&y+zz<=t[x].second)
{
pq.push({x,y+zz,xx});
continue;
}
else
{
// pair<int,int> target={zz,x+1};
// auto pp=lower_bound(st[yy].begin(),st[yy].end(),target,cmp);
// if(pp!=st[yy].end()&&pp->first>=zz&&pp->second>=x+1)
// {
// pq.push({pp->second,zz,xx});
// }
pair<int,int> target = {zz, x + 1};
auto pp = lower_bound(st[yy].begin(), st[yy].end(), target, [](const pair<int, int>& a, const pair<int, int>& b) {
if (a.first != b.first) return a.first < b.first;
return a.second < b.second;
});
if (pp != st[yy].end() && pp->first >= zz && pp->second >= x + 1) {
pq.push({pp->second, zz, xx});
}
// 暴力
// for(j=x+1;j<=k;j++)
// {
// if(t[j].first==yy&&t[j].second>=zz)
// {
// pq.push({j,zz,xx});
// break;
// }
// }
}
}
}
for(i=1;i<=n;i++){printf("%d",vis[i]);}
printf("\n");
}
int main()
{
int tt;
scanf("%d",&tt);
while(tt--){solve();}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3800kb
input:
2 5 6 4 1 2 1 30 2 3 1 50 2 5 5 50 3 4 6 10 2 4 5 30 2 5 1 40 1 70 6 100 5 40 1 30 3 1 1 2 3 1 10 1 100
output:
11011 100
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 98ms
memory: 5616kb
input:
1110 46 80 30 44 23 5 46 10 28 1 64 32 34 3 40 9 36 1 26 15 14 5 95 38 19 2 34 2 17 4 183 10 38 2 81 5 15 2 83 31 38 3 100 40 30 1 53 41 10 1 193 29 20 5 18 14 41 3 78 8 16 5 74 46 13 3 78 44 28 3 45 1 40 3 133 5 32 1 108 22 26 2 83 10 38 1 77 11 40 1 11 17 21 2 66 41 46 3 98 9 36 2 25 40 18 1 19 27...
output:
1000000000000000100010000000010000000000000000 1000000010000001010010000000001000000000000000 1000000000000000000000000000000000000000000000 1011000000000000000100000010000000000000000010 1000000000000000000000001000010000000001000000 1001100010010000100001100000000011001010110 100010000000000000000...
result:
wrong answer 1st lines differ - expected: '1000110011110111110010100001010100100101000000', found: '1000000000000000100010000000010000000000000000'