NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2004國中組決賽
 NPSC 2004 國決 G.交通運輸

作者 主題: NPSC 2004 國決 G.交通運輸  (閱讀 429 次)

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
NPSC 2004 國決 G.交通運輸
« 於: 五月 26, 2015, 10:26:24 pm »

代碼: [選擇]
// npsc04-j2g (NPSC 2004 國中決賽 題目 G 交通運輸)
// (1) 求每個節點 s 至其它節點的距離 d[s][k], k=1~n
// (2) 但 n<=1000 不可以用 n^3的方法,n節點n-1個邊,應是樹,節點i至j的路徑為唯一
// (3) 應該還有更好的方法,找每2節點之間距離,我用bfs,請熱心人士提供較佳解法
// (4) 找出每2節點的距離後, 計算 sumof(每兩節點i至j的距離 {i<j} ),再乘2即可

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 1010;
int d[maxn][maxn];
vector<int> v[maxn];
queue <int> q;
bool used[maxn];

void bfs(int s)
{
int k=q.front();
q.pop();
for(int i=0; i<v[k].size(); ++i) // 所有 k 的相鄰點
{
int j=v[k][i];
if(!used[j])
{
used[j]=true;
q.push(j);
if(!d[s][j]) d[s][j] = d[s][k]+d[k][j];
}
}
if(!q.empty()) bfs(s);
}

int main()
{
  int i,j,k , n,t;
  int a,b,c;
  cin >> t;
  while(t--)
  {
  cin >> n;
  memset(d,0,sizeof(d));
  for(i=1;i<=n;++i) v[i].clear();
for(i=1;i<n;++i)
{
cin >> a >> b >> c;
d[a][b] = d[b][a ]= c;
v[a].push_back(b);
v[b].push_back(a);
}
  for(int s=1; s<=n; ++s)
  {
  memset(used,0,sizeof(used));
q.push(s); used[s]=true;
bfs(s);  // 節點 s 至其它節點的距離 d[s][k], k=1~n
}
int sum=0;
for(i=1;i<n;++i)
for(j=i+1;j<=n;++j)
sum += d[i][j];
cout << 2*sum << endl;
}
  return 0;
}
/*
範例輸入:
4
5
1 2 5
2 3 10
3 4 3
3 5 1
2
1 2 10
7
6 1 9
1 5 5
1 3 8
3 2 7
5 4 6
4 7 3
7
6 1 9
1 5 5
5 3 8
3 2 7
5 4 6
4 7 3
範例輸出:
192
20
628
608
*/
« 上次編輯: 五月 26, 2015, 10:29:20 pm 由 rscpp »
記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2004國中組決賽
 NPSC 2004 國決 G.交通運輸