P1119 灾后重建

提交 24.32k

通过 8.03k

时间限制 1.00s

内存限制 125.00MB

题目提供者洛谷

难度提高+/省选-

历史分数100

提交记录

查看题解

题目背景

输入输出样例

输入 #1

输出 #1

-1
-1
5
4

思路

　　从Floyd中转点的本质入手，利用Floyd本身的动态规划特性处理中转点来更新 dis[i][j] ，数据也确实做到了蓝题的水准。

CODE

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 template<class T>inline void read(T &res)
 10 {
 11     char c;T flag=1;
 12     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 13     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 14 }
 15 
 16 namespace _buff {
 17     const size_t BUFF = 1 << 19;
 18     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 19     char getc() {
 20         if (ib == ie) {
 21             ib = ibuf;
 22             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 23         }
 24         return ib == ie ? -1 : *ib++;
 25     }
 26 }
 27 
 28 int qread() {
 29     using namespace _buff;
 30     int ret = 0;
 31     bool pos = true;
 32     char c = getc();
 33     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 34         assert(~c);
 35     }
 36     if (c == '-') {
 37         pos = false;
 38         c = getc();
 39     }
 40     for (; c >= '0' && c <= '9'; c = getc()) {
 41         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 42     }
 43     return pos ? ret : -ret;
 44 }
 45 
 46 const int maxn = 200 + 7;
 47 const int inf  = 0x3f3f3f3f;
 48 
 49 int n,m,s,t;
 50 int dis[maxn][maxn];
 51 int day[maxn];
 52 
 53 void floyd(int k) {
 54     for (int i = 0; i < n; ++i) {
 55         for ( int j = 0; j < n; ++j ) {
 56             if(dis[i][j] > dis[i][k] + dis[k][j]) {
 57                 dis[i][j] = dis[j][i] = dis[i][k] + dis[k][j];
 58             }
 59         }
 60     }    
 61 }
 62 
 63 int main()
 64 {
 65     scanf("%d %d",&n, &m);
 66     for ( int i = 0; i < n; ++i ) {
 67         read(day[i]);
 68     }
 69     int a, b, c;
 70     for(int i = 0; i < n; ++i) {
 71         for (int j = 0; j < n; ++j) {
 72             if(i == j) {
 73                 dis[i][j] = dis[j][i] = 0;
 74             }
 75             else {
 76                 dis[i][j] = dis[j][i] = inf;
 77             }
 78         }
 79     }
 80     for (int i = 1; i <= m; ++i) {
 81         scanf("%d %d %d",&a, &b, &c);
 82         dis[a][b] = dis[b][a] = c;
 83     }
 84     int q;
 85     read(q);
 86     int x, y;
 87     int sum = 0;
 88     for ( int i = 1; i <= q; ++i ) {
 89         scanf("%d %d %d",&x, &y, &t);
 90         if(t < day[x] || t < day[y]) {
 91             puts("-1");
 92         }
 93         else {
 94             while(day[sum] <= t && n > sum) {
 95                 floyd(sum);
 96                 sum++;
 97             }
 98             int ans = dis[x][y];
 99             if(ans == inf) {
100                 puts("-1");
101             }
102             else {
103                 printf("%d\n",ans);
104             }
105         }
106     }
107     return 0;
108 }