QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#790119#7883. Takeout DeliveringaYi_7TL 551ms123016kbC++171.6kb2024-11-28 01:21:462024-11-28 01:21:49

Judging History

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

  • [2024-11-28 01:21:49]
  • 评测
  • 测评结果:TL
  • 用时:551ms
  • 内存:123016kb
  • [2024-11-28 01:21:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>node[2000009];

 map<array<int,3>,int>dis;
const int maxn=3e9+7;

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
       int a,b,w;
       scanf("%d%d%d",&a,&b,&w);
       node[a].push_back(make_pair(b,w));
       node[b].push_back(make_pair(a,w));
    }
    priority_queue<array<int,4>,vector<array<int,4>>,greater<array<int,4>>>qq;
    //qq.push({0,0,0,0});
   // for(int i=1;i<=n;i++)
   // {
       //dis[i]=3e9+7;
   // }
    //dis[1]=0;
    qq.push({0,1,0,0});
    dis[{1,0,0}]=0;
    int juli=maxn;
    while(!qq.empty())
    {
       auto [val,nd,fst,lst]=qq.top();
       qq.pop();
       for(int i=0;i<node[nd].size();i++)
       {
           int tmpfst=fst,tmplst=lst;
           auto [b,w]=node[nd][i];
           if(w>=tmpfst)
           {
              tmplst=tmpfst;
              tmpfst=w;
           }
           else if(w>=tmplst)
           {
             tmplst=w;
           }

           int ds;
           if(dis.find({b,tmpfst,tmplst})!=dis.end()) ds=dis[{b,tmpfst,tmplst}];
            else  ds=maxn;
            if(ds>tmpfst+tmplst)
            {
               dis[{b,tmpfst,tmplst}]=tmpfst+tmplst;
               qq.push({tmpfst+tmplst,b,tmpfst,tmplst});
               if(b==n) juli=min(juli,tmpfst+tmplst);
            }
           //if(dis[b]>=tmpfst+tmplst)
           //{
            //  dis[b]=tmpfst+tmplst;
            //  qq.push({dis[b],b,tmpfst,tmplst});
           //}
       }
    }
    printf("%d\n",juli);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 50960kb

input:

4 6
1 2 2
1 3 4
1 4 7
2 3 1
2 4 3
3 4 9

output:

5

result:

ok 1 number(s): "5"

Test #2:

score: 0
Accepted
time: 551ms
memory: 123016kb

input:

300000 299999
80516 80517 597830404
110190 110191 82173886
218008 218009 954561262
250110 250111 942489774
66540 66541 156425292
34947 34948 239499776
273789 273790 453201232
84428 84429 439418398
98599 98600 326095035
55636 55637 355015760
158611 158612 684292473
43331 43332 43265001
171621 171622 ...

output:

1999991697

result:

ok 1 number(s): "1999991697"

Test #3:

score: -100
Time Limit Exceeded

input:

300000 299999
207226 231742 414945003
84591 210444 175968953
46327 51582 612565723
18773 141119 82562646
76139 286963 762958587
131867 224820 928900783
215240 216181 405340417
144725 290878 195350550
267216 268752 846015171
31413 255927 389339642
45219 147512 489502910
113391 215402 555706684
53359 ...

output:


result: