hw4

                Never    
C++
       
#include <bits/stdc++.h>
using namespace std;

typedef struct Node{
    string name, type;
    vector<int> to, msg;
} Node; // node structure

double len_ans = numeric_limits<double>::max(); // shortest path
string ord_ans; // answer sequence
int msg_ans; // answer message
bool walked[100010] = {0}; // mark walked node
Node* node[100010]; // nodes of the graph

// travel function: 
// carries -> sequence, message sum, path length, node index
void walk(string ord, int msg_sum, double len_sum, int idx){
    if(node[idx]->type == "HQ"){ // arrives at hq
        if(len_sum < len_ans){ // renew answer
            ord_ans = ord; msg_ans = msg_sum; len_ans = len_sum;
        } return;
    }
    for(int i = 0; i<node[idx]->to.size(); i++){
        if(!walked[node[idx]->to[i]] && // is node wasn't visited
           ((node[idx]->type != "CIV" && node[node[idx]->to[i]]->type != "SPY") || // spy can't go to spy
            (node[idx]->type == "CIV" && node[node[idx]->to[i]]->type != "HQ"))){ // civ can't go to hq
            walked[node[idx]->to[i]] = 1; // mark next point
            walk(ord+" -> "+node[node[idx]->to[i]]->name, // renew sequence
                 msg_sum+node[idx]->msg[i], // renew message
                 len_sum+round(1000/(double)node[idx]->msg[i]*100)/100, // renew path length
                 node[idx]->to[i]); // go to next node
            walked[node[idx]->to[i]] = 0; // path don't work, unmark point
        }
    } return;
}

int main(){
    string mov;
    int cnt = 1, stp = 0;
    while(cin >> mov){
        if(mov == "INSERT"){
            node[cnt] = new Node; // create node
            cin >> node[cnt]->type >> node[cnt++]->name;
            // check if node is starting point
            if(node[cnt-1]->type == "SOURCE") stp = cnt-1;
        } else if(mov == "INSERT_EDGE"){ // create edge
            int a, b, c; cin >> a >> b >> c;
            // connect nodes and record massage between them
            node[a]->to.push_back(b); node[a]->msg.push_back(c);
            node[b]->to.push_back(a); node[b]->msg.push_back(c);
        } else{
            // sort connected nodes so will visit by smallest order
            for(int i = 1; i<cnt; i++){
                for(int k = 0; k<node[i]->to.size()-1; k++)
                for(int j = k; j<node[i]->to.size()-1; j++){
                    if(node[i]->to[j+1] < node[i]->to[j]){
                        swap(node[i]->to[j], node[i]->to[j+1]);
                        swap(node[i]->msg[j], node[i]->msg[j+1]);
                    }
                }
            }

            walk(node[stp]->name, 0, 0, stp); // travel graph
            cout << ord_ans << endl << msg_ans << endl << len_ans << endl; // output

            break;
        }
    }

    return 0;
}

Raw Text