社区讨论

这个最后输出有啥问题吗

P1113[USACO02FEB] 杂务参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mhjajlyc
此快照首次捕获于
2025/11/03 23:24
4 个月前
此快照最后确认于
2025/11/03 23:24
4 个月前
查看原帖
CPP
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N = 1e4+5;
struct Node{
	int nxt, w;
};
vector<Node> e[N];
vector<int> topo;
int n, dp[N]; 
int edge_p[N];
void toposort(){
	queue<int> q;
	for(int i = 1; i <= n; i++)
		if(edge_p[i] == 0)
			q.push(i); 
	while(!q.empty()){
		int t = q.front();
		q.pop();
		cout << t << "\n";
		topo.push_back(t); 
		for(int i = 0; i < e[t].size(); i++){
			if(--edge_p[e[t][i].nxt] == 0)
				q.push(e[t][i].nxt);
		}
	}
	return ;
} 
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		int u, len;
		cin >> u >> len;
		while(1){
			int v;
			cin >> v;
			if(v == 0)
				break;
			e[u].push_back({v, len});
			edge_p[v]++;
		}
	} 
	toposort();
	memset(dp, 0x3f, sizeof(dp));
	dp[1] = 0;
	for(int i = topo.size()-1; i >= 0; i--){
		int u = topo[i];
		for(int j = 0; j < e[u].size(); j++){
			dp[e[u][j].nxt] = min(dp[e[u][j].nxt], dp[u] + e[u][j].w); 
		}
		
	}
/*	for(int i = 1; i <= n; i++)
		cout << dp[i] << ' ';
	cout << "\n";*/
	//cout << topo[topo.size()-1] << "\n"; 
	cout << dp[topo[topo.size()-1]];
	return 0;
} 

回复

0 条回复,欢迎继续交流。

正在加载回复...