开学，考试耽误了一段时间，最近在做简单的题找手感。今天这个题也是最近比较正式的做的一个题，而且这个题是一个johnson的模板题，通过这个题我学会了如何用迪杰斯特拉算法求边权为负的最短路。不得不说johnson算法确实十分的巧妙，今天初学理解不深。它在原有点的基础上加一个虚点，初始化它到每个点的距离都是0，然后用spfa算法（可以优化，并同时判断是否有负环）求一下虚点到每个点的距离。到i点的距离记为h[i]。若每条边的起始点记为s，指向点记为t。这条边的距离加上h[s]-h[t]，因为加这个数字是常数，所以并不影响他们之间最短路，这个距离必定为正（具体原因自己想）。然后再跑一边迪杰斯特拉即可。具体代码如下。
#include<cmath> #include <iostream> #include<stdio.h> #include<string> #include<string.h> #include<vector> #include<set> #include<map> #include<cstring> #include<math.h> #include<stack> #include<algorithm> #include<queue> #include<bitset> #include<sstream> #define ll long long int const ll mod=20123; using namespace std; ll a[5010],b[5020],c[5020],n,m,tot=0,dist[5010],dis[5010],zh[5010]; priority_queue<pair<ll,ll> >p; deque<ll> q; struct node { ll next,y,w,x; }t[20010]; void add(ll x,ll y,ll z) { t[++tot].next=a[x]; t[tot].x=x; t[tot].w=z; t[tot].y=y; a[x]=tot; } int main() { ios::sync_with_stdio(false); ll i=0,j,flat=0,x,k,y,z; cin>>n>>m; for(i=0;i<=n;i++) a[i]=-1; for(i=0;i<m;i++) { cin>>x>>y>>z; add(x,y,z); } memset(zh,0,sizeof(zh)); memset(c,0,sizeof(c)); q.push_back(0); b[0]=1; c[0]++; for(i=0;i<=n;i++) dis[i]=1; for(i=1;i<=n;i++) add(0,i,0); dis[0]=0; while(!q.empty()) { ll xp=q.front(); q.pop_front(); b[xp]=0; if(c[xp]>n) { flat=1; } if(flat) break; for(j=a[xp];j!=-1;j=t[j].next) { if(dis[t[j].y]>dis[xp]+t[j].w) { dis[t[j].y]=dis[xp]+t[j].w; if(b[t[j].y]==0) { q.push_back(t[j].y); b[t[j].y]=1; c[t[j].y]++; } } } } if(flat) { cout<<-1; } else { for(i=1;i<=n;i++) zh[i]=dis[i]; for(i=0;i<=tot;i++) { t[i].w+=zh[t[i].x]-zh[t[i].y]; } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { dis[j]=1000000000; } memset(b,0,sizeof(b)); dis[i]=0; p.push(make_pair(0,i)); b[i]=0; while(!p.empty()) { ll xp=p.top().second; p.pop(); if(b[xp]) continue; b[xp]=1; for(j=a[xp];j!=-1;j=t[j].next) { if(dis[t[j].y]>dis[xp]+t[j].w) { dis[t[j].y]=dis[xp]+t[j].w; p.push(make_pair(-dis[t[j].y],t[j].y)); } } } for(j=1;j<=n;j++) { if(dis[j]<1e9) { dis[j]+=zh[j]-zh[i]; } dist[i]+=dis[j]*j; } } for(i=1;i<=n;i++) cout<<dist[i]<<endl; } return 0; }这个题一看是个最短路，但是这个路的长短和平常的长短不一样。若俩点距离为2的幂次，则需要一步可到，所以我们只需要计算哪些点可以一步到，用动态规划的思想可以解决。最后再跑最短路即可。数据规模不大，所以用佛洛依德算法即可。代码如下。
#include<cmath> #include <iostream> #include<stdio.h> #include<string> #include<string.h> #include<vector> #include<set> #include<map> #include<cstring> #include<math.h> #include<stack> #include<algorithm> #include<queue> #include<bitset> #include<sstream> #define ll long long int const ll mod=20123; using namespace std; ll a[5010],n,m,tot=0,dis[60][60],b[60][60][100]; priority_queue<pair<ll,ll> >p; struct node { ll next,y,w,x; }t[20010]; void add(ll x,ll y,ll z) { t[++tot].next=a[x]; t[tot].x=x; t[tot].w=z; t[tot].y=y; a[x]=tot; } int main() { ios::sync_with_stdio(false); ll i=0,j,flat=0,x,k,y,z; cin>>n>>m; memset(dis,0x3f,sizeof(dis)); for(i=1;i<=m;i++) { cin>>x>>y; dis[x][y]=1; b[x][y][0]=1; } for(x=1;x<=64;x++) { for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { for(k=1;k<=n;k++) { if(b[j][i][x-1]&&b[i][k][x-1]) { dis[j][k]=1; b[j][k][x]=1; } } } } } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) dis[j][k]=min(dis[j][k],dis[j][i]+dis[i][k]); cout<<dis[1][n]; return 0; }