Untitled
unknown
c_cpp
a year ago
2.1 kB
4
Indexable
// DFS AC (6/6) 40ms #include <iostream> #include <vector> #include <string> #include <climits> using namespace std; class edge{ public: edge(int S,int D,int C,int A):S(S),D(D),C(C),A(A){} int S; int D; int C; int A; }; string command; vector<vector<edge>> M; vector<int> min_cost(215,INT_MAX); void add_edge(){ int U,V,P,A; cin >> U >> V >> P >> A; bool check = false; for(auto &it:M[U]){ if(it.D == V && it.A == A) { it.C = P; check = true; break; } } if(!check) M[U].push_back(edge(U,V,P,A)); return ; } void delete_edge(){ int U,V,A; cin >> U >> V >> A; for(auto it = M[U].begin();it!=M[U].end();it++){ if(it->D == V && it->A == A) { M[U].erase(it--); break; } } return ; } int request_route(int S,int &D,int &W,int C,int A){ if(C > W) return -1; if(S==D) return C; int ans = INT_MAX,tmp = INT_MAX; for(auto &i:M[S]){ if(ans < C + i.C) continue; else if(A!=i.A && C + i.C + 5 > W) continue; else if(A==i.A && C + i.C > W) continue; else { int cost_change = (A==-1 || i.A==A)?0:5; int total_cost = C + cost_change + i.C; if(total_cost < min_cost[i.D]) { min_cost[i.D] = total_cost; tmp = request_route(i.D,D,W,total_cost,i.A); } if(tmp != -1) ans = min(ans,tmp); } } return (ans<=W)?ans:-1; } int main(){ std::ios::sync_with_stdio(false); cin.tie(0); int C; cin>>C; M.resize(C); int step; cin>>step; while(step--){ fill(min_cost.begin(),min_cost.end(),INT_MAX); cin>>command; if(command=="Add") add_edge(); else if(command=="Delete") delete_edge(); else { int S,D,W; cin >> S >> D >> W; cout << request_route(S,D,W,0,-1) << '\n'; } } return 0; }
Editor is loading...
Leave a Comment