【题解】

2025-07-29 20:20:46

发布于：广东

23阅读

0回复

0点赞

~~精DJ落泪~~
这题要用铃铛人（bushi
或者SPFA（带负）代码如下：

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

const int N = 1e3 + 5;
const int INF = 0x3c;
vector<pair<int,int> > g[N];
//我这里用的是pair，struct也可以
int dist[N],vis[N];
//dist不用多说，vis是用来判断负环的

int main(){
    int n,m,s;
    cin >> n >> m >> s;
    for(int i = 1;i <= m;i ++){
        int u,v,w;
        cin >> u >> v >> w;
        g[u].push_back({v,w});
        //attention：有向图
    }
    queue<int> q;
    memset(dist,INF,sizeof dist);
    //dist数组初始化为正无穷，好在松弛的时候直接比较
    dist[s] = 0;
    q.push(s);
    while(!q.empty()){
        int ip = q.front();
        q.pop();
        vis[ip] ++;
        if(vis[ip] > n){
            //图中n个点，这代表如果最坏时每个点都对此松弛一遍，也不会松弛超过n次。因此必有负环。
            cout << "no solution";
            return 0;
        }
        for(auto node : g[ip]){
            int v = node.first,w = node.second;
            if(dist[v] > dist[ip] + w){//如果优于之前的路线就松弛。
                dist[v] = dist[ip] + w;
                q.push(v);
            }
        }
    }
    for(int i = 1;i <= n;i ++){
        if(dist[i] == 0x3c3c3c3c) cout << "-1 ";//差点忘了输出-1，即正无穷时
        else cout << dist[i] << " ";
    }
    return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 1

我好菜啊不会写c++谁能教教我

dj能过

1周前来自广东

我好菜啊不会写c++谁能教教我

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e3+10;
ll n,m,s,cnt,head[N],d[N],dd[N];
ll mx=(1<<31)-1;
struct lsqxx{
	int v,w,nxt;
}l[2*N];
void add(int u,int v,int w){
	cnt++;
	l[cnt].v=v;
	l[cnt].w=w;
	l[cnt].nxt=head[u];
	head[u]=cnt;
}
void dj(ll s){
	priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>q; 
	q.push({0,s});d[s]=0;
	while(q.size()){
		pair<ll,ll>p=q.top();q.pop();
		ll u=p.second,di=p.first;
		if(di!=d[u])continue;
        dd[u]++;
        if(dd[u]>=n){
            cout<<"no solution";
            exit(0);
        }
		for(int i=head[u];i!=0;i=l[i].nxt){
			ll v=l[i].v,w=l[i].w;
			if(d[v]>di+w){
				d[v]=di+w;
				q.push({d[v],v});
			}
		}
	}
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		ll u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
	for(int i=1;i<=n;i++)d[i]=mx;dj(s);
	for(int i=1;i<=n;i++){
        if(d[i]==mx)cout<<-1<<" ";
        else cout<<d[i]<<" ";
    }
	return 0;
}

1周前来自广东