C++ WZOI P2833农场派对

农场派对

提交数: 183, 通过率: 13.11%, 平均分: 69.28

题目描述:

N头牛都要去参加一场在编号为X（1≤X≤N）的牛的农场举行的派对（1≤N≤3000），农场之间有M（1≤M≤100，000）条有向路，每条路长Ti（1≤Ti≤100）。

每头牛参加派对后都必须回到家，每头牛都会选择最短路。求这N头牛的最短路（一个来回）中最长的一条的长度。

输入格式:

第一行，3个空格分开的整数N,M,X。

第二行到M+1行： 3个用空格分开的整数Ai，Bi，Ti，表示有一条从Ai到Bi的路，长度为Ti。

输出格式:

一行，最长的最短路的长度。

样例输入:

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

样例输出:

10

时间限制: 1000ms
空间限制: 256MB

这道题我看了很多博客代码，结果在WZOI上都TLE90挂掉，下面代码爱搬走搬走~  我就不说了

摘要

本题要求计算所有从各自农场前往编号为 X 的牛的农场参加派对并返回的牛中，最短往返路径长度的最大值。农场之间由 M 条有向道路连接，每条道路都有对应的长度，每头牛都会选择往返的最短路径。目标是找到这些最短路径中最长的一个距离。

关键点

• N头牛（1≤N≤3000）需要参加在编号为X的牛的农场举行的派对。
• 农场之间有M条有向道路（1≤M≤100,000），每条道路长度为Ti（1≤Ti≤100）。
• 每头牛在参加派对后都必须返回自己的农场。
• 每头牛都会选择从自己农场到X号农场的最短路径，以及返回的最短路径。
• 问题要求找出所有牛的往返最短路径中长度最长的一条。
• 输入包括农场数量、道路数量、派对农场编号，以及每条道路的详细信息。
• 输出需要计算并输出最长的最短往返路径长度。

  #include <bits/stdc++.h>  
  using namespace std;  
  
  #define PII pair<int, int>  
  #define INF INT_MAX   // 使用系统的最大值定义  
  const int N = 3005;  // 修改为3005以涵盖1到3000的所有节点  
  int dis[N][2], n, x, m;  
  struct Node {  
      int v, w;  
  };  
  vector<Node> E[2][N];  
  bool vis[N];  
  
  void DJ(int s, int loc) {  
      memset(vis, 0, sizeof vis);  
      
      priority_queue<PII, vector<PII>, greater<PII>> que;  
      que.push({0, s});  
      dis[s][loc] = 0;  
  
      while (!que.empty()) {  
          int t = que.top().second;  
          que.pop();  
          if (vis[t]) continue;  
          vis[t] = true;  
  
          for (Node &node : E[loc][t]) {  
              int j = node.v;  
              int w = node.w;  
              // 我们只在未访问的节点上更新距离  
              if (dis[j][loc] > dis[t][loc] + w) {  
                  dis[j][loc] = dis[t][loc] + w;  
                  que.push({dis[j][loc], j});  
              }  
          }  
      }  
  }  
  
  int main() {  
      memset(dis, 0x3f, sizeof dis);  // Initialize distances to a large number  
      cin >> n >> m >> x;  
      int u, v, w;  
      for (int i = 0; i < m; ++i) {  
          cin >> u >> v >> w;  
          E[0][u].push_back({v, w});  // Build the forward graph  
          E[1][v].push_back({u, w});  // Build the reverse graph  
      }  
  
      // Calculate shortest path from X to all nodes (forward direction)  
      DJ(x, 0);  
      // Calculate shortest path from all nodes to X (reverse direction)  
      DJ(x, 1);  
  
      int ans = 0;  
      // Calculate the longest shortest round trip distance  
      for (int i = 1; i <= n; ++i)  
          ans = max(dis[i][0] + dis[i][1], ans);  
  
      cout << ans << endl;  
  
      return 0;  
  }