本题的思路是用dijkstra一遍图中的每个点。但由于有负边。我们需要将其转正。
这时需要建立一个超级源点。令其与每个点相连且距离为0。spfa一遍求出每个点到源点的最短距离dis【i】(可能为负数)
然后修改每条边的权值为w【i~j】+dis【i】-dis【j】(i到j的边)。
由于i~j的最短路径为w【i~j】。故dis【j】<=dis【i】+w【i~j】。故移项即可保证w【i~j】的值为正。
且最后结果为常数偏移只要每个点+dis【j】-dis【i】即可得到答案(证明见题解吧qwq(比如势能那个解释就奇奇怪怪的但看起来又挺靠谱的亚子orz))
AC代码如下:
#include <algorithm> #include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<queue> #define MAXN 3005 #define inf 1e9 using namespace std; typedef long long ll; typedef pair<int,int> pii; vector<pii>g[MAXN]; int n,m,temp1,temp2,temp3,dis[MAXN],cnt[MAXN],vis[MAXN],dist[MAXN]; bool spfa(){ memset(cnt,0,sizeof(cnt)); memset(dis,0x3f3f3f3f,sizeof(dis)); dis[0]=0; queue<int>q; q.push(0); vis[0]=1; while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(int i=0;i<g[u].size();i++){ int v=g[u][i].second; int w=g[u][i].first; if(dis[v]>dis[u]+w){ dis[v]=dis[u]+w; if(!vis[v]){ q.push(v); vis[v]=1; cnt[v]=cnt[u]+1; if(cnt[v]>=n) return 0; } } } } return 1; } void dijkstra(int k){ priority_queue<pii,vector<pii>,greater<pii> >q; q.push(make_pair(0,k)); ll ans=0; for(int i=1;i<=n;i++){ vis[i]=0; dist[i]=inf; } dist[k]=0; while(!q.empty()){ int u=q.top().second; q.pop(); if(vis[u]) continue; vis[u]=1; for(int i=0;i<g[u].size();i++){ int w=g[u][i].first; int v=g[u][i].second; if(dist[v]>dist[u]+w) dist[v]=dist[u]+w; if(!vis[v]) q.push(make_pair(dist[v],v)); } } for(int i=1;i<=n;i++){ if(dist[i]==inf){ ans+=i*inf; continue; } ans=ans+(1ll*i*(dist[i]+dis[i]-dis[k])); } printf("%lld\n",ans); } int main(){ scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("%d%d%d",&temp1,&temp2,&temp3); g[temp1].push_back(make_pair(temp3,temp2));//first为边权,second为下一节点。 } for(int i=1;i<=n;i++) g[0].push_back(make_pair(0,i));//建立超级源点 if(!spfa()){ printf("-1"); return 0; } for(int i=1;i<=n;i++) for(int j=0;j<g[i].size();j++){ g[i][j].first+=dis[i]-dis[g[i][j].second]; } 对于( int i= 1 ;i<=n;i++ ){ 迪杰斯特拉(一); } 返回 0 ; }
联系客服