- 每次只能带一样东西
- 求送完这 (N−1) 样东西并且最终回到邮局最少需要多少时间。
这几个关键句暗示我们：这道题需要求最短路。
我们将总路径拆成两类。
- 第一类是由邮局（节点(1)）发散出来的最短路径和。这一类显然是单源最短路径和。
- 第二类是由其他店到邮局（节点(1)）的路径和。这一类处理方法比较困难，下面罗列出我在比赛时的两种处理方法。
部分分
每个点都跑一次Dijkstra，再求出两点之间的最短路径和。此方法有大量冗余计算，效率低下，复杂度为(O(n^2 log_2n))。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1005,M=1e5+5;
struct edge {
int to,w,nxt;
} e[M];
int n,tmp,head[N],vis[N],dis[N];
void add(int x,int y,int z) {
e[++tmp].to=y,e[tmp].w=z,e[tmp].nxt=head[x],head[x]=tmp;
}
priority_queue<pair<int,int>> q;
inline void dijkstra(int u) {
priority_queue<pair<int,int>> q;
memset(dis,0x7f,sizeof(dis));
memset(vis,0,sizeof(vis));
q.push(make_pair(0,u)),dis[u]=0;
while(q.size()) {
u=q.top().second,q.pop();
if(vis[u]) {
continue;
}
vis[u]=1;
for(int i=head[u],v,w; i; i=e[i].nxt) {
v=e[i].to,w=e[i].w;
if(dis[u]+w<dis[v]) {
dis[v]=dis[u]+w;
q.push(make_pair(-dis[v],v));
}
}
}
}
int main() {
int m;
scanf("%d %d",&n,&m);
for (int i=0,u,v,w; i<m; i++) {
scanf("%d %d %d",&u,&v,&w);
add(u,v,w);
}
memset(dis,0x7f,sizeof(dis));
dijkstra(1);
int ans=0;
for(int i=2; i<=n; i++) {
ans+=dis[i];
}
for(int i=2; i<=n; i++) {
dijkstra(i),ans+=dis[1];
}
printf("%d",ans);
return 0;
}
正解
我们需要一种新的方法。
在求第二类路径和时，我们发现：如果我们对这个图建反图，那么第二类路径和类似于第一类路径和。我们可以用同样的时间复杂度（(O(n log_2n))）求解，不会超时。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1005,M=1e5+5;
int n;
namespace P1 {
struct edge {
int to,w,nxt;
} e[M];
int tmp,head[N],vis[N],dis[N];
void add(int x,int y,int z) {
e[++tmp].to=y,e[tmp].w=z,e[tmp].nxt=head[x],head[x]=tmp;
}
priority_queue<pair<int,int>> q;
inline void dijkstra(int u) {
priority_queue<pair<int,int>> q;
memset(dis,0x7f,sizeof(dis));
memset(vis,0,sizeof(vis));
q.push(make_pair(0,u)),dis[u]=0;
while(q.size()) {
u=q.top().second,q.pop();
if(vis[u]) {
continue;
}
vis[u]=1;
for(int i=head[u],v,w; i; i=e[i].nxt) {
v=e[i].to,w=e[i].w;
if(dis[u]+w<dis[v]) {
dis[v]=dis[u]+w;
q.push(make_pair(-dis[v],v));
}
}
}
}
}
namespace P2 {
struct edge {
int to,w,nxt;
} e[M];
int tmp,head[N],vis[N],dis[N];
void add(int x,int y,int z) {
e[++tmp].to=y,e[tmp].w=z,e[tmp].nxt=head[x],head[x]=tmp;
}
priority_queue<pair<int,int>> q;
inline void dijkstra(int u) {
priority_queue<pair<int,int>> q;
memset(dis,0x7f,sizeof(dis));
memset(vis,0,sizeof(vis));
q.push(make_pair(0,u)),dis[u]=0;
while(q.size()) {
u=q.top().second,q.pop();
if(vis[u]) {
continue;
}
vis[u]=1;
for(int i=head[u],v,w; i; i=e[i].nxt) {
v=e[i].to,w=e[i].w;
if(dis[u]+w<dis[v]) {
dis[v]=dis[u]+w;
q.push(make_pair(-dis[v],v));
}
}
}
}
}
int main() {
int m;
scanf("%d %d",&n,&m);
for (int i=0,u,v,w; i<m; i++) {
scanf("%d %d %d",&u,&v,&w);
P1::add(u,v,w),P2::add(v,u,w);
}
memset(P1::dis,0x7f,sizeof(P1::dis));
memset(P2::dis,0x7f,sizeof(P2::dis));
P1::dijkstra(1),P2::dijkstra(1);
int ans=0;
for(int i=2; i<=n; i++) {
ans+=P1::dis[i]+P2::dis[i];
}
printf("%d",ans);
return 0;
}
后记
在这道题里，要注意计算冗余量是否够多（类似时间复杂度）。这道题一开始的时间复杂度(O(n^2 log_2n))与后来的(O(n log_2n))区别还是很大的，例如我的提交记录：
所以说：注意时间复杂度！