NC14292. Travel
描述
精灵王国有N座美丽的城市，它们以一个环形排列在Bzeroth的大陆上。其中第i座城市到第i+1座城市花费的时间为d[i]。特别地，第N座城市到第1座城市花费的时间为d[N]。这些道路都是双向的。
另外，精灵们在数千年的时间里建造了M座传送门，第i座传送门连接了城市u[i]与城市v[i]，并且需要花费w[i]的时间通过（可能有两座传送门连接了同一对城市，也有可能一座传送门连接了相同的两座城市）。这些传送门都是双向的。
小S是精灵王国交通部部长，她的职责是为精灵女王设计每年的巡查路线。每次陛下会从某一个城市到达另一个城市，沿路调查每个城市的治理情况，她需要找出一条用时最短的路线。
输入描述
第一行为2个整数N、M。
第二行为N个正整数d[i]。
接下来M行每行三个正整数u[i]、v[i]、w[i]。
第M+3行为一个正整数Q，表示需要设计路线的次数。
接下来Q行每行两个正整数x、y，表示一次从城市x到城市y的旅行。
输出描述
Q行每行一个正整数表示该次旅行的最短时间。
示例1
输入:
4 1 1 2 3 6 1 3 2 5 1 2 1 4 1 3 2 3 4 3
输出:
1 5 2 2 3
C++(g++ 7.5.0) 解法, 执行用时: 59ms, 内存消耗: 13424K, 提交时间: 2022-11-03 23:46:10
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int n, m;
const int N = 6 * (1e4 + 5), M = N * 2;
int ne[M], e[M], h[N], w[M],
a, b, c, idx, qu;
LL sum[N];
LL dist[22][N];
queue<int>q;
bool st[N];
void add(int a, int b,int c) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
void spfa(int a, LL g[]) {
memset(st, 0, sizeof st);
while (q.size()) {
int u = q.front();
q.pop();
st[u] = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int son = e[i];
if (g[son] > g[u] + w[i]) {
g[son] = g[u] + w[i];
if (st[son])continue;
st[son] = 1;
q.push(son);
}
}
}
}
int main() {
memset(h, -1, sizeof h);
cin >> n >> m;
memset(dist, 0x3f, sizeof dist);
for (int i = 1; i <= n; i++) {
scanf("%d", &a);
if (i == n)add(i, 1, a), add(1, i, a);
else add(i, i + 1, a), add(i + 1, i, a);
sum[i+1] = a + sum[i];
}
int cnt = 0;
while (m--) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
dist[cnt][a] = 0;
//dist[cnt][b] = 0;
//q.push(b);
q.push(a);
spfa(cnt, dist[cnt]);
cnt++;
}
cin >> qu;
while (qu--) {
scanf("%d%d", &a, &b);
//没有传送门时
if (a > b)swap(a, b);
LL ans = min(sum[b] - sum[a],
sum[n + 1] - (sum[b] - sum[a]));
//有传送门时
for (int i = 0; i < cnt;i++) {
ans = min(ans, dist[i][a] + dist[i][b]);
}
printf("%lld\n", ans);
}
return 0;
}
C++14(g++5.4) 解法, 执行用时: 195ms, 内存消耗: 3092K, 提交时间: 2020-07-15 21:14:19
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,ans,a[200010],f[101][101],sum[200010],id[200010],cnt;
map<ll,ll>mp;
ll get(ll l,ll r){
if(l>r)swap(l,r);
return min(sum[r-1]-sum[l-1],sum[n]-sum[r-1]+sum[l-1]);
}
int main(){
ll t1,i,j,k,x,y,w;
scanf("%lld%lld",&n,&m);
for(i=1;i<=50;i++)
for(j=1;j<=50;j++)f[i][j]=1e18;
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
for(i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
for(i=1;i<=m;i++){
scanf("%lld%lld%lld",&x,&y,&w);
if(!mp[x])mp[x]=++cnt,id[cnt]=x;
if(!mp[y])mp[y]=++cnt,id[cnt]=y;
x=mp[x];y=mp[y];
f[x][y]=f[y][x]=min(f[x][y],w);
}
for(i=1;i<=cnt;i++)
for(j=1;j<=cnt;j++)f[i][j]=f[j][i]=min(f[i][j],get(id[i],id[j]));
for(k=1;k<=cnt;k++)
for(i=1;i<=cnt;i++)
for(j=1;j<=cnt;j++)f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
scanf("%lld",&t1);
while(t1--){
scanf("%lld%lld",&x,&y);
ans=get(x,y);
for(i=1;i<=cnt;i++)
for(j=1;j<=cnt;j++)ans=min(ans,get(x,id[i])+get(y,id[j])+f[i][j]);
printf("%lld\n",ans);
}
}
C++11(clang++ 3.9) 解法, 执行用时: 326ms, 内存消耗: 2140K, 提交时间: 2020-01-05 15:11:07
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,ans,a[200010],f[101][101],sum[200010],id[200010],cnt;
map<ll,ll>mp;
ll get(ll l,ll r){
if(l>r)swap(l,r);
return min(sum[r-1]-sum[l-1],sum[n]-sum[r-1]+sum[l-1]);
}
int main(){
ll t1,i,j,k,x,y,w;
scanf("%lld%lld",&n,&m);
for(i=1;i<=50;i++)
for(j=1;j<=50;j++)f[i][j]=1e18;
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
for(i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
for(i=1;i<=m;i++){
scanf("%lld%lld%lld",&x,&y,&w);
if(!mp[x])mp[x]=++cnt,id[cnt]=x;
if(!mp[y])mp[y]=++cnt,id[cnt]=y;
x=mp[x];y=mp[y];
f[x][y]=f[y][x]=min(f[x][y],w);
}
for(i=1;i<=cnt;i++)
for(j=1;j<=cnt;j++)f[i][j]=f[j][i]=min(f[i][j],get(id[i],id[j]));
for(k=1;k<=cnt;k++)
for(i=1;i<=cnt;i++)
for(j=1;j<=cnt;j++)f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
scanf("%lld",&t1);
while(t1--){
scanf("%lld%lld",&x,&y);
ans=get(x,y);
for(i=1;i<=cnt;i++)
for(j=1;j<=cnt;j++)ans=min(ans,get(x,id[i])+get(y,id[j])+f[i][j]);
printf("%lld\n",ans);
}
}