2025年C++數(shù)據(jù)結(jié)構(gòu)機試題及答案【問題描述】任務(wù)調(diào)度系統(tǒng)需要處理動態(tài)添加的任務(wù)及其依賴關(guān)系，并支持查詢從指定起始任務(wù)開始的最短完成總時間（即關(guān)鍵路徑長度）。每個任務(wù)有唯一的ID和執(zhí)行時間，任務(wù)執(zhí)行前需完成所有前置任務(wù)。系統(tǒng)需支持以下兩種操作：1.添加任務(wù)：格式為"ADD<任務(wù)ID><執(zhí)行時間><前置任務(wù)數(shù)><前置任務(wù)ID列表>"（若前置任務(wù)數(shù)為0，則列表為空）2.查詢?nèi)蝿?wù)：格式為"QUERY<起始任務(wù)ID>"，輸出從該起始任務(wù)開始，完成所有可執(zhí)行任務(wù)的最短總時間（即所有可能路徑中的最長路徑長度）輸入保證：-所有任務(wù)ID為字符串，由字母和數(shù)字組成，長度不超過10-執(zhí)行時間為正整數(shù)-添加任務(wù)時，所有前置任務(wù)已存在-任務(wù)依賴關(guān)系構(gòu)成有向無環(huán)圖（DAG）【輸入樣例】5ADDA30ADDB21AADDC41AADDD52BCQUERYA【輸出樣例】12【答案】```cppinclude<iostream>include<unordered_map>include<vector>include<queue>include<string>include<algorithm>include<climits>usingnamespacestd;structTask{inttime;vector<string>preds;vector<string>succs;};unordered_map<string,Task>tasks;vector<string>get_reachable(conststring&start){vector<string>reachable;if(tasks.find(start)==tasks.end())returnreachable;unordered_map<string,bool>visited;queue<string>q;q.push(start);visited[start]=true;reachable.push_back(start);while(!q.empty()){stringu=q.front();q.pop();for(conststring&v:tasks[u].succs){if(!visited[v]){visited[v]=true;reachable.push_back(v);q.push(v);}}}returnreachable;}vector<string>topological_sort(constvector<string>&nodes){unordered_map<string,int>in_degree;unordered_map<string,vector<string>>adj;for(conststring&u:nodes){adj[u]=tasks[u].succs;in_degree[u]=0;for(conststring&p:tasks[u].preds){if(find(nodes.begin(),nodes.end(),p)!=nodes.end()){in_degree[u]++;}}}queue<string>q;for(conststring&u:nodes){if(in_degree[u]==0){q.push(u);}}vector<string>topo;while(!q.empty()){stringu=q.front();q.pop();topo.push_back(u);for(conststring&v:adj[u]){if(find(nodes.begin(),nodes.end(),v)!=nodes.end()){in_degree[v]--;if(in_degree[v]==0){q.push(v);}}}}returntopo;}intquery(conststring&start){vector<string>reachable=get_reachable(start);if(reachable.empty())return0;vector<string>topo=topological_sort(reachable);if(topo.size()!=reachable.size())return0;unordered_map<string,int>dp;intmax_time=0;for(conststring&u:reachable){dp[u]=INT_MIN;}dp[start]=tasks[start].time;max_time=dp[start];for(conststring&u:topo){for(conststring&v:tasks[u].succs){if(find(reachable.begin(),reachable.end(),v)!=reachable.end()){if(dp[v]<dp[u]+tasks[v].time){dp[v]=dp[u]+tasks[v].time;if(dp[v]>max_time){max_time=dp[v];}}}}}returnmax_time;}intmain(){intn;cin>>n;stringop;while(n--){cin>>op;if(op=="ADD"){stringid;intt,k;cin>>id>>t>>k;Tasktask;task.time=t;for(inti=0;i<k;++i){stringpred;cin>>pred;task.preds.push_back(pred);tasks[pred].succs.push_back(id);}