思路：
此题真的恐怖。心态得到了升华。差分约束类（详见：），正权单向最短路Dijkstra。我心目中的正解是两遍DIJKSTRA的，但是WA了。用 cin 关同步一直血T，scanf 就超快。没有必要用 pair，结构体比它快。全部松弛后再取值，中间取值由于判断次数过多，反而运行时间更长。
代码：
心目中的正解：WA
#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std
;
const int maxn
= 30005;
struct NODE
{
int id
;
int dis
;
friend bool operator
> (NODE a
,NODE b
){
return a
.dis
> b
.dis
;
}
NODE(int id
,int dis
) : id(id
) , dis(dis
) {} ;
};
priority_queue
<NODE
, vector
<NODE
> , greater
<NODE
> > Q
;
int N
,M
;
struct EDGE
{
int to
;
int w
;
int fo
;
};
EDGE E
[maxn
* 5];
int tail
[maxn
];
void ADDEDGE(int i
,int u
,int v
,int w
){
E
[i
].to
= v
;
E
[i
].w
= w
;
E
[i
].fo
= tail
[u
];
tail
[u
] = i
;
return ;
}
int dis
[maxn
];
int IJK(int s
,int e
){
memset(dis
,INF
,sizeof(dis
));
Q
.push(NODE(s
,0));dis
[s
]=0;
while(Q
.size()){
NODE cur
= Q
.top() ; Q
.pop() ;
if(cur
.dis
> dis
[cur
.id
])
continue;
for(int i
=tail
[cur
.id
];~i
;i
=E
[i
].fo
){
if(dis
[E
[i
].to
] > dis
[cur
.id
] + E
[i
].w
){
dis
[E
[i
].to
] = dis
[cur
.id
] + E
[i
].w
;
Q
.push(NODE(E
[i
].to
, dis
[E
[i
].to
]));
}
}
}
return dis
[e
];
}
int main(){
memset(tail
,-1,sizeof(tail
));
scanf("%d %d",&N
, &M
);
int u
,v
,w
;
for(int i
=1;i
<=M
;i
++){
scanf("%d %d %d",&u
,&v
,&w
);
ADDEDGE(i
,u
,v
,w
);
}
cout
<<max(IJK(1,N
) , IJK(N
,1))<<endl
;
return 0;
}
用pair会更慢：625ms 2680kB
#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
#define INF 0x3f3f3f3f
using namespace std
;
const int maxn
= 30005;
typedef pair
<int,int> Ptype
;
priority_queue
<Ptype
, vector
<Ptype
> , greater
<Ptype
> > Q
;
int N
,M
;
struct EDGE
{
int to
;
int w
;
int fo
;
};
EDGE E
[maxn
* 5];
int tail
[maxn
];
void ADDEDGE(int i
,int u
,int v
,int w
){
E
[i
].to
= v
;
E
[i
].w
= w
;
E
[i
].fo
= tail
[u
];
tail
[u
] = i
;
return ;
}
int dis
[maxn
];
int IJK(){
memset(dis
,INF
,sizeof(dis
));
Q
.push(Ptype(0,1));dis
[1]=0;
int fi
,se
;
while(Q
.size()){
Ptype cur
= Q
.top() ; Q
.pop() ;
fi
= cur
.first
;
se
= cur
.second
;
if(fi
> dis
[se
])
continue;
for(int i
=tail
[se
];~i
;i
=E
[i
].fo
){
if(dis
[E
[i
].to
] > dis
[se
] + E
[i
].w
){
dis
[E
[i
].to
] = dis
[se
] + E
[i
].w
;
Q
.push(Ptype(dis
[E
[i
].to
] , E
[i
].to
));
}
}
}
return dis
[N
];
}
int main(){
memset(tail
,-1,sizeof(tail
));
scanf("%d %d",&N
, &M
);
int u
,v
,w
;
for(int i
=1;i
<=M
;i
++){
scanf("%d %d %d",&u
,&v
,&w
);
ADDEDGE(i
,u
,v
,w
);
}
cout
<<IJK()<<endl
;
return 0;
}
用结构体最快：579ms 2680kB
#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
#define INF 0x3f3f3f3f
using namespace std
;
const int maxn
= 30005;
struct NODE
{
int id
;
int dis
;
friend bool operator
> (NODE a
,NODE b
){
return a
.dis
> b
.dis
;
}
NODE(int id
,int dis
) : id(id
) , dis(dis
) {} ;
};
priority_queue
<NODE
, vector
<NODE
> , greater
<NODE
> > Q
;
int N
,M
;
struct EDGE
{
int to
;
int w
;
int fo
;
};
EDGE E
[maxn
* 5];
int tail
[maxn
];
void ADDEDGE(int i
,int u
,int v
,int w
){
E
[i
].to
= v
;
E
[i
].w
= w
;
E
[i
].fo
= tail
[u
];
tail
[u
] = i
;
return ;
}
int dis
[maxn
];
int IJK(){
memset(dis
,INF
,sizeof(dis
));
Q
.push(NODE(1,0));dis
[1]=0;
int fi
,se
;
while(Q
.size()){
NODE cur
= Q
.top() ; Q
.pop() ;
if(cur
.dis
> dis
[cur
.id
])
continue;
for(int i
=tail
[cur
.id
];~i
;i
=E
[i
].fo
){
if(dis
[E
[i
].to
] > dis
[cur
.id
] + E
[i
].w
){
dis
[E
[i
].to
] = dis
[cur
.id
] + E
[i
].w
;
Q
.push(NODE(E
[i
].to
, dis
[E
[i
].to
]));
}
}
}
return dis
[N
];
}
int main(){
memset(tail
,-1,sizeof(tail
));
scanf("%d %d",&N
, &M
);
int u
,v
,w
;
for(int i
=1;i
<=M
;i
++){
scanf("%d %d %d",&u
,&v
,&w
);
ADDEDGE(i
,u
,v
,w
);
}
cout
<<IJK()<<endl
;
return 0;
}
在松弛过程中判断比较慢：641ms 2689kB
int IJK(){
memset(dis
,INF
,sizeof(dis
));
Q
.push(NODE(1,0));dis
[1]=0;
int fi
,se
;
while(Q
.size()){
NODE cur
= Q
.top() ; Q
.pop() ;
if(cur
.id
== N
)
return dis
[N
];
if(cur
.dis
> dis
[cur
.id
])
continue;
for(int i
=tail
[cur
.id
];~i
;i
=E
[i
].fo
){
if(dis
[E
[i
].to
] > dis
[cur
.id
] + E
[i
].w
){
dis
[E
[i
].to
] = dis
[cur
.id
] + E
[i
].w
;
Q
.push(NODE(E
[i
].to
, dis
[E
[i
].to
]));
}
}
}
}
