Nail9 @ 2024-03-31 10:46:32
dijkstra和优先队列,弱化版全部AC,标准版3,4,6WA
测试点3输出和答案文件比较:
文件在位置 162779 处不同.
文件1位置 162774 附近的10个字节:7 25488 25
文件2位置 162774 附近的10个字节:7 25800 25
文件在位置 167856 处不同.
文件1位置 167851 附近的10个字节: 26212 255
文件2位置 167851 附近的10个字节: 26212 256
文件在位置 167857 处不同.
文件1位置 167852 附近的10个字节:26212 2552
文件2位置 167852 附近的10个字节:26212 2569
文件在位置 167858 处不同.
文件1位置 167853 附近的10个字节:6212 25527
文件2位置 167853 附近的10个字节:6212 25698
文件在位置 229428 处不同.
文件1位置 229423 附近的10个字节: 26054 252
文件2位置 229423 附近的10个字节: 26054 258
文件在位置 229429 处不同.
文件1位置 229424 附近的10个字节:26054 2525
文件2位置 229424 附近的10个字节:26054 2582
文件在位置 229430 处不同.
文件1位置 229425 附近的10个字节:6054 25259
文件2位置 229425 附近的10个字节:6054 25820
文件在位置 282864 处不同.
文件1位置 282859 附近的10个字节: 26455 253
文件2位置 282859 附近的10个字节: 26455 257
文件在位置 282865 处不同.
文件1位置 282860 附近的10个字节:26455 2535
文件2位置 282860 附近的10个字节:26455 2574
文件在位置 282866 处不同.
文件1位置 282861 附近的10个字节:6455 25357
文件2位置 282861 附近的10个字节:6455 25746
源码:
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define ulli unsigned long long int
const int MAX=2147483647;
const int MAXnline=200005+9;
//const int MAXnline=50;
const int MAXnpoint=100005+9;
//const int MAXnpoint=50;
vector<long long int> Alength(MAXnpoint,MAX);
vector<int> Ahead(MAXnpoint,-1);
bool visited[MAXnpoint];
struct nodeA{
int pend,w,bro;
}datum[MAXnline];
int last=0;
struct nodepq{
int point,length;
bool operator<(const nodepq& other) const{
return length>other.length;
}
};
priority_queue<nodepq> wait;
int main(){
// freopen("P4779_3.in","r",stdin);
// freopen("out.txt","w",stdout);
int npoint,nline,fpoint;
scanf("%d %d %d",&npoint,&nline,&fpoint);
int tempa,tempb,tempc;
for(int iout=1;iout<=nline;iout++){
scanf("%d %d %d",&tempa,&tempb,&tempc);
datum[last].pend=tempb;
datum[last].w=tempc;
datum[last].bro=Ahead[tempa];
Ahead[tempa]=last;
last++;
}
Alength[fpoint]=0;
nodepq tempnode;
tempnode.point=fpoint;
tempnode.length=0;
wait.push(tempnode);
while(!wait.empty()){
int topp=wait.top().point;
wait.pop();
if(visited[topp])
continue;
visited[topp]=true;
int thisloc=Ahead[topp];
while(true){
long long int toppTOthisloc=datum[thisloc].w;
int thisp=datum[thisloc].pend;
if(Alength[thisp]>toppTOthisloc+Alength[topp]){
Alength[thisp]=toppTOthisloc+Alength[topp];
tempnode.point=thisp;
tempnode.length=Alength[thisp];
if(!visited[thisp])
wait.push(tempnode);
}
if(datum[thisloc].bro==-1)
break;
thisloc=datum[thisloc].bro;
}
}
for(int i=1;i<=npoint;i++){
printf("%d ",Alength[i]);
}
return 0;
}
by ENJOuYang @ 2024-03-31 12:18:24
// 1.
printf("%d ",Alenth[i]);
// 应为
//printf("%lld",Alenth[i]);
// 2.
int thisloc=Ahead[topp];
while(true){
/*代码段*/
}
// 应为
// int thisloc=Ahead[topp];
// if(thisloc==-1)
// continue;
// while(true){
// /*代码段*/
// }
by ENJOuYang @ 2024-03-31 12:20:06
%lld后面少了个空格
by Nail9 @ 2024-04-02 20:37:52
@ENJOuYang 谢大佬orz