import java.util.Scanner;
public class Main {
public static void main(String[] arg) {
Scanner scanner = new Scanner(System.in);
// todo
}
}
NC21530. Accel World
描述
输入描述
There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:
The first line contains three integers n, m and k (2 ≤ n ≤ 100, 1 ≤ m ≤ 8000, 0 ≤ k ≤ n) -- the number of vertices, the number of edges and the number of special vertices.
Each of the following m lines contains three integers ui, vi and wi (1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 1000) denoting an edge with wi unit length connecting ui and vi.
The next line contains k integers p1,p2,...,pk (1 ≤ pi ≤ n) denoting the index of each \textit{acceleration vertex}.
It's guaranteed that the sum of n over all test cases will not exceed 1000 and the sum of m over all test cases will not exceed 80000.
输出描述
For each test case, output a real number t denoting the minimum time to reach the vertex n and an integer s denoting the maximum times of acceleration Chiaki can achieve among all optimal solutions.
Your answer for t will be considered correct if and only if the absolute error or relative error of your answer is less than 10-8. And by the way, if s is greater than 32767, output ``Burst!'' (without the quotes) instead.
示例1
输入:
3 2 1 2 1 2 1 1 2 5 4 2 1 2 1 2 3 1 3 4 1 4 5 1 2 3 6 7 2 1 2 2 2 4 2 4 6 2 1 3 2 3 4 2 4 5 4 5 6 4 3 4
输出:
0.5000000000 2 2.0000000000 Burst! 3.5000000000 2
C++14(g++5.4) 解法, 执行用时: 350ms, 内存消耗: 1128K, 提交时间: 2018-12-01 17:20:25
#include <bits/stdc++.h>int N, M, K;__int128 dis[200][200];int buf[200];__int128 dp[200][200];__int128 pow2[120];int clo[200];int main () {pow2[0] = 1;for (int i = 1; i < 120; ++i) pow2[i] = pow2[i - 1] * 2;int T; scanf ("%d", &T); while (T--) {scanf ("%d%d%d", &N, &M, &K);for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) dis[i][j] = pow2[119];for (int i = 1; i <= N; ++i) dis[i][i] = 0;for (int i = 1; i <= M; ++i) {int u, v, w;scanf ("%d%d%d", &u, &v, &w);dis[u][v] = dis[v][u] = std::min (dis[u][v], w * pow2[100]);}for (int i = 1; i <= K; ++i) scanf ("%d", &buf[i]);for (int k = 1; k <= N; ++k)for (int i = 1; i <= N; ++i)for (int j = 1; j <= N; ++j)dis[i][j] = std::min (dis[i][j], dis[i][k] + dis[k][j]);for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) dp[i][j] = pow2[119];for (int i = 1; i <= K; ++i) dp[1][i] = dis[1][buf[i]];for (int i = 1; i <= N; ++i) for (int j = 1; j <= K; ++j) for (int k = 1; k <= K; ++k) if (j != k)dp[i + 1][k] = std::min (dp[i + 1][k], dp[i][j] + dis[buf[j]][buf[k]] / pow2[i]);for (int i = 1; i <= K; ++i) {clo[i] = 0;for (int j = 1; j <= K; ++j) if (i != j) {if (clo[i] == 0 || dis[buf[i]][buf[clo[i]]] > dis[buf[i]][buf[j]]) clo[i] = j;}}std::pair <__int128, int> res = std::make_pair (dis[1][N], 0);for (int i = 1; i <= N; ++i) for (int j = 1; j <= K; ++j) {res = std::min (res, std::make_pair (dp[i][j] + dis[buf[j]][N] / pow2[i], -i));if (K > 1)res = std::min (res, std::make_pair (dp[i][j] + dis[buf[j]][buf[clo[j]]] / pow2[i] * 2, -40000));}if (res.second < -32767)printf ("%.10f Burst!\n", (double) ((__float128) res.first / pow2[100]));elseprintf ("%.10f %d\n", (double) ((__float128) res.first / pow2[100]), -res.second);}}
C++11(clang++ 3.9) 解法, 执行用时: 386ms, 内存消耗: 1132K, 提交时间: 2018-12-09 15:51:47
#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>using namespace std;typedef __int128 LL;typedef __float128 LD;const int Lim=105;const int N=205;const LL MAX=(LL)1<<124;int n,m,k;LL f[N][N];LL Pow[105];LL dp[N][N];int p[N];int tot=0;int main(){Pow[0]=1; for (int u=1;u<=Lim;u++) Pow[u]=Pow[u-1]*2LL;int T;scanf("%d",&T);while (T--){scanf("%d%d%d",&n,&m,&k);for (int u=1;u<=n;u++)for (int i=1;i<=n;i++)f[u][i]=MAX;f[1][1]=0;tot=0;for (int u=1;u<=m;u++){int x,y,w;scanf("%d%d%d",&x,&y,&w);f[x][y]=min(f[x][y],w*Pow[Lim]);f[y][x]=f[x][y];//printf("YES:%d %lld %lld\n",w,Pow[Lim],f[x][y]);}for (int u=1;u<=k;u++){scanf("%d",&p[u]);if (p[u]==n) tot++;}for (int u=1;u<=n;u++)for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)f[i][j]=min(f[i][j],f[i][u]+f[u][j]);for (int u=1;u<=n;u++) dp[0][u]=f[1][u];LL ans=f[1][n],ans1=0;/* for (int i=1;i<=n;i++) printf("%lf ",(double)dp[0][i]/Pow[Lim]);printf("\n");*/for (int u=1;u<Lim;u++){for (int i=1;i<=n;i++) dp[u][i]=MAX;for (int i=1;i<=k;i++){int now=p[i];for (int j=1;j<=n;j++){if (now==j) continue;dp[u][j]=min(dp[u][j],dp[u-1][now]+f[now][j]/Pow[u]);//printf("YES:%d %d %lf\n",now,j,(double)dp[u][j]/Pow[Lim]);}}/*for (int i=1;i<=n;i++) printf("%lf ",(double)dp[u][i]/Pow[Lim]);printf("\n");*/if (dp[u][n]<=ans) {ans=dp[u][n],ans1=u;}//printf("%d %lf\n",u,(double)dp[u][n]/Pow[Lim]);}//printf("%lld %lf\n",ans,(double)ans/Pow[Lim]);if (ans1>=Lim-2) printf("%.10lf Burst!\n",(double)((LD)ans/Pow[Lim]));else printf("%.10lf %d\n",(double)((LD)ans/Pow[Lim]),ans1+tot);}return 0;}