关于这题的 Special Judge
查看原帖
关于这题的 Special Judge
126582
Scintilla楼主2020/8/6 10:15

第二个测试点，我构造的数据是

99
98 1 100000 2 100000 3 100000 4 100000 5 100000 6 100000 7 100000 8 100000 9 100000 10 100000 11 100000 12 100000 13 100000 14 100000 15 100000 16 100000 17 100000 18 100000 19 100000 20 100000 21 100000 22 100000 23 100000 24 100000 25 100000 26 100000 27 100000 28 100000 29 100000 30 100000 31 100000 32 100000 33 100000 34 100000 35 100000 36 100000 37 100000 38 100000 39 100000 40 100000 41 100000 42 100000 43 100000 44 100000 45 100000 46 100000 47 100000 48 100000 49 100000 50 100000 51 100000 52 100000 53 100000 54 100000 55 100000 56 100000 57 100000 58 100000 59 100000 60 100000 61 100000 62 100000 63 100000 64 100000 65 100000 66 100000 67 100000 68 100000 69 100000 70 100000 71 100000 72 100000 73 100000 74 100000 75 100000 76 100000 77 100000 78 100000 79 100000 80 100000 81 100000 82 100000 83 100000 84 100000 85 100000 86 100000 87 100000 88 100000 89 100000 90 100000 91 100000 92 100000 93 100000 94 100000 95 100000 96 100000 97 100000 98 1 
98 0 1 2 100000 3 100000 4 100000 5 100000 6 100000 7 100000 8 100000 9 100000 10 100000 11 100000 12 100000 13 100000 14 100000 15 100000 16 100000 17 100000 18 100000 19 100000 20 100000 21 100000 22 100000 23 100000 24 100000 25 100000 26 100000 27 100000 28 100000 29 100000 30 100000 31 100000 32 100000 33 100000 34 100000 35 100000 36 100000 37 100000 38 100000 39 100000 40 100000 41 100000 42 100000 43 100000 44 100000 45 100000 46 100000 47 100000 48 100000 49 100000 50 100000 51 100000 52 100000 53 100000 54 100000 55 100000 56 100000 57 100000 58 100000 59 100000 60 100000 61 100000 62 100000 63 100000 64 100000 65 100000 66 100000 67 100000 68 100000 69 100000 70 100000 71 100000 72 100000 73 100000 74 100000 75 100000 76 100000 77 100000 78 100000 79 100000 80 100000 81 100000 82 100000 83 100000 84 100000 85 100000 86 100000 87 100000 88 100000 89 100000 90 100000 91 100000 92 100000 93 100000 94 100000 95 100000 96 100000 97 100000 98 100000 
98 0 100000 1 1 3 100000 4 100000 5 100000 6 100000 7 100000 8 100000 9 100000 10 100000 11 100000 12 100000 13 100000 14 100000 15 100000 16 100000 17 100000 18 100000 19 100000 20 100000 21 100000 22 100000 23 100000 24 100000 25 100000 26 100000 27 100000 28 100000 29 100000 30 100000 31 100000 32 100000 33 100000 34 100000 35 100000 36 100000 37 100000 38 100000 39 100000 40 100000 41 100000 42 100000 43 100000 44 100000 45 100000 46 100000 47 100000 48 100000 49 100000 50 100000 51 100000 52 100000 53 100000 54 100000 55 100000 56 100000 57 100000 58 100000 59 100000 60 100000 61 100000 62 100000 63 100000 64 100000 65 100000 66 100000 67 100000 68 100000 69 100000 70 100000 71 100000 72 100000 73 100000 74 100000 75 100000 76 100000 77 100000 78 100000 79 100000 80 100000 81 100000 82 100000 83 100000 84 100000 85 100000 86 100000 87 100000 88 100000 89 100000 90 100000 91 100000 92 100000 93 100000 94 100000 95 100000 96 100000 97 100000 98 100000 
98 0 100000 1 100000 2 1 4 100000 5 100000 6 100000 7 100000 8 100000 9 100000 10 100000 11 100000 12 100000 13 100000 14 100000 15 100000 16 100000 17 100000 18 100000 19 100000 20 100000 21 100000 22 100000 23 100000 24 100000 25 100000 26 100000 27 100000 28 100000 29 100000 30 100000 31 100000 32 100000 33 100000 34 100000 35 100000 36 100000 37 100000 38 100000 39 100000 40 100000 41 100000 42 100000 43 100000 44 100000 45 100000 46 100000 47 100000 48 100000 49 100000 50 100000 51 100000 52 100000 53 100000 54 100000 55 100000 56 100000 57 100000 58 100000 59 100000 60 100000 61 100000 62 100000 63 100000 64 100000 65 100000 66 100000 67 100000 68 100000 69 100000 70 100000 71 100000 72 100000 73 100000 74 100000 75 100000 76 100000 77 100000 78 100000 79 100000 80 100000 81 100000 82 100000 83 100000 84 100000 85 100000 86 100000 87 100000 88 100000 89 100000 90 100000 91 100000 92 100000 93 100000 94 100000 95 100000 96 100000 97 100000 98 100000 
98 0 100000 1 100000 2 100000 3 1 5 100000 6 100000 7 100000 8 100000 9 100000 10 100000 11 100000 12 100000 13 100000 14 100000 15 100000 16 100000 17 100000 18 100000 19 100000 20 100000 21 100000 22 100000 23 100000 24 100000 25 100000 26 100000 27 100000 28 100000 29 100000 30 100000 31 100000 32 100000 33 100000 34 100000 35 100000 36 100000 37 100000 38 100000 39 100000 40 100000 41 100000 42 100000 43 100000 44 100000 45 100000 46 100000 47 100000 48 100000 49 100000 50 100000 51 100000 52 100000 53 100000 54 100000 55 100000 56 100000 57 100000 58 100000 59 100000 60 100000 61 100000 62 100000 63 100000 64 100000 65 100000 66 100000 67 100000 68 100000 69 100000 70 100000 71 100000 72 100000 73 100000 74 100000 75 100000 76 100000 77 100000 78 100000 79 100000 80 100000 81 100000 82 100000 83 100000 84 100000 85 100000 86 100000 87 100000 88 100000 89 100000 90 100000 91 100000 92 100000 93 100000 94 100000 95 100000 96 100000 97 100000 98 100000 
98 0 100000 1 100000 2 100000 3 100000 4 1 6 100000 7 100000 8 100000 9 100000 10 100000 11 100000 12 100000 13 100000 14 100000 15 100000 16 100000 17 100000 18 100000 19 100000 20 100000 21 100000 22 100000 23 100000 24 100000 25 100000 26 100000 27 100000 28 100000 29 100000 30 100000 31 100000 32 100000 33 100000 34 100000 35 100000 36 100000 37 100000 38 100000 39 100000 40 100000 41 100000 42 100000 43 100000 44 100000 45 100000 46 100000 47 100000 48 100000 49 100000 50 100000 51 100000 52 100000 53 100000 54 100000 55 100000 56 100000 57 100000 58 100000 59 100000 60 100000 61 100000 62 100000 63 100000 64 100000 65 100000 66 100000 67 100000 68 100000 69 100000 70 100000 71 100000 72 100000 73 100000 74 100000 75 100000 76 100000 77 100000 78 100000 79 100000 80 100000 81 100000 82 100000 83 100000 84 100000 85 100000 86 100000 87 100000 88 100000 89 100000 90 100000 91 100000 92 100000 93 100000 94 100000 95 100000 96 100000 97 100000 98 100000 
98 0 100000 1 100000 2 100000 3 100000 4 100000 5 1 7 100000 8 100000 9 100000 10 100000 11 100000 12 100000 13 100000 14 100000 15 100000 16 100000 17 100000 18 100000 19 100000 20 100000 21 100000 22 100000 23 100000 24 100000 25 100000 26 100000 27 100000 28 100000 29 100000 30 100000 31 100000 32 100000 33 100000 34 100000 35 100000 36 100000 37 100000 38 100000 39 100000 40 100000 41 100000 42 100000 43 100000 44 100000 45 100000 46 100000 47 100000 48 100000 49 100000 50 100000 51 100000 52 100000 53 100000 54 100000 55 100000 56 100000 57 100000 58 100000 59 100000 60 100000 61 100000 62 100000 63 100000 64 100000 65 100000 66 100000 67 100000 68 100000 69 100000 70 100000 71 100000 72 100000 73 100000 74 100000 75 100000 76 100000 77 100000 78 100000 79 100000 80 100000 81 100000 82 100000 83 100000 84 100000 85 100000 86 100000 87 100000 88 100000 89 100000 90 100000 91 100000 92 100000 93 100000 94 100000 95 100000 96 100000 97 100000 98 100000 
98 0 100000 1 100000 2 100000 3 100000 4 100000 5 100000 6 1 8 100000 9 100000 10 100000 11 100000 12 100000 13 100000 14 100000 15 100000 16 100000 17 100000 18 100000 19 100000 20 100000 21 100000 22 100000 23 100000 24 100000 25 100000 26 100000 27 100000 28 100000 29 100000 30 100000 31 100000 32 100000 33 100000 34 100000 35 100000 36 100000 37 100000 38 100000 39 100000 40 100000 41 100000 42 100000 43 100000 44 100000 45 100000 46 100000 47 100000 48 100000 49 100000 50 100000 51 100000 52 100000 53 100000 54 100000 55 100000 56 100000 57 100000 58 100000 59 100000 60 100000 61 100000 62 100000 63 100000 64 100000 65 100000 66 100000 67 100000 68 100000 69 100000 70 100000 71 100000 72 100000 73 100000 74 100000 75 100000 76 100000 77 100000 78 100000 79 100000 80 100000 81 100000 82 100000 83 100000 84 100000 85 100000 86 100000 87 100000 88 100000 89 100000 90 100000 91 100000 92 100000 93 100000 94 100000 95 100000 96 100000 97 100000 98 100000 
98 0 100000 1 100000 2 100000 3 100000 4 100000 5 100000 6 100000 7 1 9 100000 10 100000 11 100000 12 100000 13 100000 14 100000 15 100000 16 100000 17 100000 18 100000 19 100000 20 100000 21 100000 22 100000 23 100000 24 100000 25 100000 26 100000 27 100000 28 100000 29 100000 30 100000 31 100000 32 100000 33 100000 34 100000 35 100000 36 100000 37 100000 38 100000 39 100000 40 100000 41 100000 42 100000 43 100000 44 100000 45 100000 46 100000 47 100000 48 100000 49 100000 50 100000 51 100000 52 100000 53 100000 54 100000 55 100000 56 100000 57 100000 58 100000 59 100000 60 100000 61 100000 62 100000 63 100000 64 100000 65 100000 66 100000 67 100000 68 100000 69 100000 70 100000 71 100000 72 100000 73 100000 74 100000 75 100000 76 100000 77 100000 78 100000 79 100000 80 100000 81 100000 82 100000 83 100000 84 100000 85 100000 86 100000 87 100000 88 100000 89 100000 90 100000 91 100000 92 100000 93 100000 94 100000 95 100000 96 100000 97 100000 98 100000 
98 0 100000 1 100000 2 100000 3 100000 4 100000 5 100000 6 100000 7 100000 8 1 10 100000 11 100000 12 100000 13 100000 14 100000 15 100000 16 100000 17 100000 18 100000 19 100000 20 100000 21 100000 22 100000 23 100000 24 100000 25 100000 26 100000 27 100000 28 100000 29 100000 30 100000 31 100000 32 100000 33 100000 34 100000 35 100000 36 100000 37 100000 38 100000 39 100000 40 100000 41 100000 42 100000 43 100000 44 100000 45 100000 46 100000 47 100000 48 100000 49 100000 50 100000 51 100000 52 100000 53 100000 54 100000 55 100000 56 100000 57 100000 58 100000 59 100000 60 100000 61 100000 62 100000 63 100000 64 100000 65 100000 66 100000 67 100000 68 100000 69 100000 70 100000 71 100000 72 100000 73 100000 74 100000 75 100000 76 100000 77 100000 78 100000 79 100000 80 100000 81 100000 82 100000 83 100000 84 100000 85 100000 86 100000 87 100000 88 100000 89 100000 90 100000 91 100000 92 100000 93 100000 94 100000 95 100000 96 100000 97 100000 98 100000 
1 9 1
1 10 1
1 11 1
1 12 1
1 13 1
1 14 1
1 15 1
1 16 1
1 17 1
1 18 1
1 19 1
1 20 1
1 21 1
1 22 1
1 23 1
1 24 1
1 25 1
1 26 1
1 27 1
1 28 1
1 29 1
1 30 1
1 31 1
1 32 1
1 33 1
1 34 1
1 35 1
1 36 1
1 37 1
1 38 1
1 39 1
1 40 1
1 41 1
1 42 1
1 43 1
1 44 1
1 45 1
1 46 1
1 47 1
1 48 1
1 49 1
1 50 1
1 51 1
1 52 1
1 53 1
1 54 1
1 55 1
1 56 1
1 57 1
1 58 1
1 59 1
1 60 1
1 61 1
1 62 1
1 63 1
1 64 1
1 65 1
1 66 1
1 67 1
1 68 1
1 69 1
1 70 1
1 71 1
1 72 1
1 73 1
1 74 1
1 75 1
1 76 1
1 77 1
1 78 1
1 79 1
1 80 1
1 81 1
1 82 1
1 83 1
1 84 1
1 85 1
1 86 1
1 87 1
1 88 1
1 89 1
1 90 1
1 91 1
1 92 1
1 93 1
1 94 1
1 95 1
1 96 1
1 97 1
10
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1

这是要放的程序：

#include <algorithm>
#include <cstdio>
using namespace std;

int i, j, k, V, n, w, M[300][300], counter, Q, s, t;

int main() {
  scanf("%d", &V);
  for (i = 0; i < V; i++)
    for (j = i+1; j < V; j++)
      M[i][j] = M[j][i] = 1000000000;
  for (i = 0; i < V; i++)
    M[i][i] = 0;

  for (i = 0; i < V; i++) {
    scanf("%d", &n);
    while (n--) {
      scanf("%d %d", &j, &w);
      M[i][j] = min(M[i][j], w);
    }
  }

  counter = 0;
  for (k = 0; k < V; k++)
    for (i = 0; i < V; i++)
      for (j = 0; j < V; j++) {
        counter++;
        if (counter > 1000000) {
          printf("TLE because iteration counter > 1000000\n");
          return 1;
        }
        M[i][j] = min(M[i][j], M[i][k] + M[k][j]);
      }

  scanf("%d", &Q);
  while (Q--) {
    scanf("%d %d", &s, &t);
    printf("%d\n", M[s][t]);
  }

  printf("The value of counter is: %d\n", counter);
  return 0;
}

这是要卡的程序：

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

typedef pair<int, int> IntPair;
typedef vector<IntPair> VectorIntPair;

#define INF 1000000000

int i, j, u, V, n, w, Q, counter, s, t;
vector<VectorIntPair> AdjList;
bool change;

int main() {
  scanf("%d", &V);
  AdjList.assign(V, VectorIntPair());
  for (i = 0; i < V; i++) {
    scanf("%d", &n);
    while (n--) {
      scanf("%d %d", &j, &w);
      AdjList[i].push_back(IntPair(j, w));


    }
  }

  counter = 0;
  scanf("%d", &Q);
  while (Q--) {
    scanf("%d %d", &s, &t);
    vector<int> dist(V, INF);
    dist[s] = 0;

    for (i = 0; i < V-1; i++) {
      change = false;
      for (u = 0; u < V; u++)
        for (j = 0; j < (int)AdjList[u].size(); j++) {
          counter++;
          if (counter > 1000000) {
            printf("TLE because iteration counter > 1000000\n");
            return 1;
          }

          IntPair v = AdjList[u][j];
          
          if (dist[u] + v.second < dist[v.first]) {
            dist[v.first] = dist[u] + v.second;
            change = true;
          }
        }
        
      if (!change) // the optimized BellmanFord
        break;
    }

    printf("%d\n", dist[t]);
  }

  printf("The value of counter is: %d\n", counter);
  return 0;
}

可是结果却是这样（我太弱了只写了前两个点）

求问，是我的问题还是这题的 SPJ 有锅？

2020/8/6 10:15