矿大数据结构 实验四_矿大数据结构4

目录

A: 机器人王国里的路径长度

B: 从源点开始的最短路径

C: 最少天数

D: 寻找第二小的数

E: 按十进制各位和排序

F: 奇偶数的排序

---

A: 机器人王国里的路径长度

如果只有单个的字母则不必用 map ，直接用 char-'A' 存储到普通数组即可。但是本题应该是不全为单个字母，所以需要用 map 存储。由于任一节点只有一个父节点，那么用数组记录每个节点的父节点即可。如果有多个父节点的话就开一个二维的 map 数组

从子节点开始遍历，直到无父节点则代表找到了首都

#include<bits/stdc++.h>
using namespace std;
map<string,string> par;
map<string,int> len;
// map <string,map<string,int> >mp   //二维map数组 
signed main(){
	int n;cin>>n;
	int m = pow(2,n+1)-2;
	
	for(int i=1;i<=m;i++){
		string s1,s2;
		int temp;
		cin>>s1>>s2>>temp;
		par[s2] = s1;
		len[s2] = temp;
	}
	
	string now;cin>>now;
	long long ans = 0;   //数据量较大，开long long 会比较稳妥 
	while(par[now].length()>0){
		ans += len[now];
		now = par[now];
	}
	cout<<ans;
	return 0;
}

B: 从源点开始的最短路径

Dijkstra 或 floyed 或 dfs 

开一个数组存储步数，不可能成为最优解的直接舍弃

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,tar;
int mp[210][210];  //地图 
//bool pd[210][210]; //这条路是否走过 |致命错误！同一条路可以重复走
long long l[210];  //源点到该点路径长度 
// 到另一个点的步数必须小于之前花的步数 
void dfs(int now,int len){
 
	if(l[now]==0||len<l[now])
		l[now] = len;
	if(now==tar){
		return;
	}
 
	for(int i=1;i<=n;i++){		
		if(i==now) continue;
		if(mp[now][i] == 0) continue;		
		if(l[i]>len+mp[now][i]|| l[i]==0) 
		{	
			dfs(i,len+mp[now][i]);
		}
	}
 
}
signed main(){
	cin>>n>>m;	
	for(int i=1;i<=m;i++){
		int x1,x2,x3;
		cin>>x1>>x2>>x3;
		if(mp[x1][x2]==0||x3<mp[x1][x2]){
			mp[x1][x2]=x3;
		}
	}
	cin>>tar;
	dfs(1,0);
	cout<<l[tar];
	return 0;
}

C: 最少天数

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <limits>
 
using namespace std;
 
// 定义图的边
struct Edge {
    char destination;
    int weight;
};
 
// 计算完成工程的最短天数
int calculateShortestTime(const unordered_map<char, vector<Edge>>& graph) {
    unordered_map<char, int> inDegree;
    unordered_map<char, int> earliestStartTime;
 
    // 统计每个事件的入度
    for (const auto& node : graph) {
        char currentNode = node.first;
        inDegree[currentNode] = 0;
        earliestStartTime[currentNode] = -1; // 初始化最早开始时间为-1
    }
 
    for (const auto& node : graph) {
        char currentNode = node.first;
        for (const Edge& edge : node.second) {
            char nextNode = edge.destination;
            inDegree[nextNode]++;
        }
    }
 
    // 初始化起点的最早开始时间为0
    earliestStartTime['A'] = 0;
 
    // 使用拓扑排序计算每个事件的最早开始时间
    queue<char> q;
    q.push('A');
 
    while (!q.empty()) {
        char currentNode = q.front();
        q.pop();
 
        auto it = graph.find(currentNode);
        if (it == graph.end()) {
            continue;
        }
 
        for (const Edge& edge : it->second) {
            char nextNode = edge.destination;
            int nextStartTime = earliestStartTime[currentNode] + edge.weight;
            earliestStartTime[nextNode] = max(earliestStartTime[nextNode], nextStartTime);
 
            if (--inDegree[nextNode] == 0) {
                q.push(nextNode);
            }
        }
    }
 
    // 返回工程的最短天数
    return earliestStartTime['Z'];
}
 
int main() {
    int N, M;
    cin >> N >> M;
    unordered_map<char, vector<Edge>> graph;
    // 读取子任务信息
    for (int i = 0; i < M; ++i) {
        char startNode, endNode;
        int weight;
        cin >> startNode >> endNode >> weight;
        graph[startNode].push_back({ endNode, weight });
    }
 
    int shortestTime = calculateShortestTime(graph);
    cout << shortestTime << endl;
 
    return 0;
}

D: 寻找第二小的数

sort

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,tar;
signed main(){
	int c;cin>>c;
	while(c--){
		int n;cin>>n;
		int a[110];
		for(int i=1;i<=n;i++){
			cin>>a[i];
		} 
		sort(a+1,a+n+1);
		bool pd = 0;
		for(int i=2;i<=n;i++){
			if(a[i]!=a[1]){
				cout<<a[i]<<endl;
				pd = 1;
				break;
			}
		}
		if(pd==0) cout<<"NO\n";
	} 
	return 0;
}
 

E: 按十进制各位和排序

自定义一个cmp，sort

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000010;
 
int a[N];
bool cmp(int m,int n){
	int x=m,y=n;
	int sm=0,sn=0;
	while(m>0){
		sm+=m%10;
		m/=10;
	}
	while(n>0){
		sn+=n%10;
		n/=10;
	}
	if(sm>sn) return 1;
	else if(sm==sn) return x>y;
	else return 0;
}
signed main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		cout<<a[i]<<' ';
	}
	return 0;
}
 

F: 奇偶数的排序

sort

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100010;
bool cmp(int m,int n){
	return m>n;
}
int n,m,tar;
int a[10010];
int odd[N];
int even[N];
signed main(){
	int oi=1,ei=1;
	for(int i=1;i<=10;i++){
		cin>>a[i];
		if(a[i]%2) odd[oi++] = a[i];
		else even[ei++] = a[i];
	}
	sort(odd+1,odd+6,cmp);
	for(int i=1;i<=5;i++){
		cout<<odd[i]<<' ';
	}
	sort(even+1,even+6);
	for(int i=1;i<=5;i++)cout<<even[i]<<' ';
	return 0;
}