方老师分身 I

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

Submit Status

方老师为了开更多讲座，于是他分身了！早上他都在某一个教室分身，然后各个分身分别赶去各个不同的n个教室（当然每个教室都要有且只有一个分身）。晚上各个分身都赶回之前分身时的教室，合并成一个人（不需要同时回去）。但是教室间的路十分崎岖，而且是单向的。当然即便只是方老师的分身，那也是相当厉害的，每个分身都会走花费时间最少的路径。方老师想知道他往返走路时间最长的那个分身所花在走路上的时间。题目保证有路可走。

Input

第一行输入三个整数 n, m, x（1≤n≤1000, 1≤m≤100,000, 1≤x≤n）。表示有n个教室，m条路，x为方老师分身的地方。

接下来m行，每行三个数，u, v, t表示从教室u到教室v存在一条单向边，花费时间t（1≤t≤100）。

Output

输出一个整数，往返中走路时间最长的分身所花费的时间。

Sample input and output

Source

2014 UESTC Training for Graph Theory

解题报告：

首先跑一次最短路，之后正解是交换所有边的顺序和代价，再跑一遍最短路即可（想想为什么）。。。当然我很傻，直接跑了N次SPFA，居然没T...

#include <iostream>

#include <algorithm>

#include <vector>

#include <cstring>

#include <cstdio>

#include <queue>

#define pb push_back

const int maxn = 1e3 + ;

typedef struct Edge

{

   int target,cost;

   Edge(const int& target,const int& cost)

   {

         this->target = target , this->cost = cost;

   }

};

using namespace std;

int mincost[maxn][maxn];

bool inqueue[maxn];

vector<Edge>E[maxn];

queue<int>q;

int n,m,x;

void bfs(int tar)

{

  q.push(tar);

  mincost[tar][tar] = ;

  while(!q.empty())

   {

          int pos = q.front();q.pop();

          inqueue[pos] = false;

          int cost = mincost[tar][pos];

          for(int i =  ; i < E[pos].size() ; ++ i)

           {

              int nextnode = E[pos][i].target;

           if (mincost[tar][nextnode] == - || mincost[tar][nextnode] > cost + E[pos][i].cost)

            {

                mincost[tar][nextnode] = cost + E[pos][i].cost;

                if (!inqueue[nextnode])

                 {

                      q.push(nextnode);

                      inqueue[nextnode] = true;

                 }

            }

        }

   }

}

int main(int argc,char *argv[])

{

  memset(mincost,-,sizeof(mincost));

  memset(inqueue,false,sizeof(inqueue));

  scanf("%d%d%d",&n,&m,&x);

  for(int i =  ; i < m ; ++ i)

   {

         int u,v,t;

         scanf("%d%d%d",&u,&v,&t);

         E[u].pb(Edge(v,t));

   }

  for(int i =  ; i <= n ; ++ i)

   bfs(i);

  int ans = ;

  for(int i =  ; i <= n ; ++ i)

   ans = max(ans , mincost[x][i] + mincost[i][x]);

  printf("%d\n",ans);

  return ;

}