前提・実現したいこと
Atcoder beginner contest 126 E問題に関する質問です。
発生している問題・エラーメッセージ
TLEになってしまい、C++初心者ゆえどこを改善したらいいか分からず、アドバイスいただきたいです。
該当のソースコード
C++
1#include <iostream> 2#include <string> 3#include <vector> 4#include <queue> 5using std::vector; 6using std::find; 7using std::distance; 8using namespace std; 9 10int findIndex(vector<int> v) { 11 //値が-1となるindexを返す 12 int key = -1; 13 int idx; 14 vector<int>::iterator itr = std::find(v.begin(), v.end(), key); 15 idx = std::distance(v.begin(), itr); 16 return idx; 17} 18 19int main() { 20 int N, M; 21 cin >> N >> M; 22 vector<vector<int>> to(N); 23 24 for(int i = 1; i <= M; ++i){ 25 int X ,Y ,Z; 26 cin >> X >> Y >> Z; 27 X--; 28 Y--; 29 to[X].push_back(Y); 30 to[Y].push_back(X); 31 } 32 33 vector<int> ans(N, -1); 34 35 ans[0] = -1; 36 int count = 0; 37 int idx = 0; 38 39 while(true){ 40 queue<int> q; 41 idx = findIndex(ans); 42 if (idx >= N)break; 43 //cout << "idx: " << idx << endl; 44 q.push(idx); 45 46 while(!q.empty()){ 47 int v = q.front(); 48 q.pop(); 49 //cout << "in the first while loop " << "v: " << v << "to[v].size()" << to[v].size() << endl; 50 if(to[v].size() == 0){ 51 //cout << "to[v].size() == 0, idx is " << idx << "and count is " << count << endl; 52 if(ans[idx] != -1) break; 53 ans[idx] = count; 54 break; 55 }else{ 56 for(int i = 0; i < to[v].size(); ++i){ 57 //cout << "size" << i << ":" << to[v].size() << endl; 58 int u = to[v][i]; 59 if(ans[u] != -1) break; 60 ans[u] = count; 61 //cout << "to[v].size() != 0, u is " << u << "and count is " << count << endl; 62 q.push(u); 63 }//end of for loop 64 }//end of else 65 }// 66 count++; 67 //cout << "count increment" << endl; 68 } 69 cout << count << endl; 70 return 0; 71}
試したこと
一つのノードから辿れるノードに同じ番号をつけ、異なる番号のものをカウントし、提出しています。
補足情報(FW/ツールのバージョンなど)
ここにより詳細な情報を記載してください。
プロファイリング結果はどうなっていますか。
あなたの回答
tips
プレビュー