[[problem:ROUTING]]
Tutorial에 그래프 Routing 문제 입니다.
다익스트라 알고리즘을 응용해서 만들었습니다.
답은 맞게 나오는 듯 한데 시간초과가 뜹니다.
알고리즘 보다는 코드에 성능측면으로 잘못되거나 비효율적인 부분이 있으면 지적해 주시길 부탁드립니다. 아주 사소한것이라도 좋습니다.
그리고

vector<vector<int>> v;

이런식의 데이터 구조는
int v[][] 와 같은 이차원 배열보다 비효율적인가요?

//2015/6/11 Algospot.com Routing 시간초과 제한시간 2000ms


#include<iostream>
#include<vector>
#include<array>

using namespace std;

struct Edge{
    int to;             //엣지와 연결된 노드
    double dist;        //엣지의 길이(noise)
    Edge( int b, double c){
        to=b;
        dist=c;
    }
    Edge(){
    }
};

class Dijkstra{
private: 
    int comNum;
    int EdgeNum;
    double *distance;
    bool *visited;
    double *result;
    vector<vector<Edge>> cango; 

public:
    Dijkstra(){
    }
    void Find(int start);
    void in();
};

void Dijkstra::in(){
    //입력 받기
    int cases;
    cin>>cases;
    int a;
    int b;
    double c;
    result = new double[cases];
    for(int i=0; i<cases; i++){
        cin>>comNum;
        cin>>EdgeNum;
        distance= new double[comNum];
        visited = new bool[comNum];
        cango.clear();
        cango.reserve(comNum);

        //cango[i] -> i에서 갈수 있는 Edge의 집합 Vector
        
        for(int j=0; j<comNum; j++){
            cango.push_back(vector<Edge>());
            visited[j]=false;
            distance[j]=0;
        }
        distance[0]=1;
        for(int j=0; j<EdgeNum; j++){
            cin>>a;
            cin>>b;
            cin>>c;
            cango[a].push_back(Edge(b,c));
            cango[b].push_back(Edge(a,c));
        }
        
        
        //답 찾기
        Find(0);
        result[i]=distance[comNum-1];
    }

    //결과 출력
    cout<<fixed;
    cout.precision(10);
    for(int i=0; i<cases; i++){
        
        cout<<result[i]<<endl;  
    }
    cin>>cases;
}

void Dijkstra::Find(int start){

    int nowLoc=start;
    int n=0;
    int to=0;
    double dis=0;
    while(n<comNum){
        visited[nowLoc]=true;
        for(int i=0; i<cango[nowLoc].size(); i++){
            to=cango[nowLoc].at(i).to;
            //현재 노드와 연결된 노드들의 distance 계산
            if(!visited[to]){
                dis=distance[nowLoc] * cango[nowLoc].at(i).dist;
                if(dis<distance[to]||distance[to]==0){
                    distance[to]=dis;
                }
            }

        }
        double min = 99999999999999;
        int loc = 0;
        double dist;

        //distance 값이 가장 작은 위치를 찾아 방문(while 문 반복)
        for(int i=0; i<comNum; i++){
            dist=distance[i];
            if(min>dist&&!visited[i]&&dist!=0){
                min = dist;
                loc = i;
            }
        }
        nowLoc = loc;
        n++;
    }
    
}

int main(){
    Dijkstra d;
    d.in();
}