算法1
(spfa) $O(NM)$
由于x都是正数,那么我们构造一个虚拟源点,用spfa求一遍最长路就可以了,
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2e5+10;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
void add(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void spfa()
{
queue<int> q;
q.push(0);
memset(dist,-0x3f,sizeof dist);
dist[0]=0;
while(q.size())
{
int t=q.front();
q.pop();
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]<dist[t]+w[i])
{
dist[j]=dist[t]+w[i];
q.push(j);
}
}
}
}
int main()
{
int n,m,c;
cin>>n>>m>>c;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
add(0,i,x);
}
for(int i=1;i<=c;i++)
{
int a,b,x;
cin>>a>>b>>x;
add(a,b,x);
}
spfa();
for(int i=1;i<=n;i++)
{
cout<<dist[i]<<endl;
}
return 0;
}
算法2
(拓扑排序) $O(N+M)$
我们知道有的时候spfa的时间复杂度会被卡到O(N*M),对于DAG,我们可以用时间复杂度为O(N+M)的拓扑排序。
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2e5+10;
int h[N],e[M],ne[M],w[M],idx;
int dist[N],d[N];
void add(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void topsort()
{
queue<int> q;
q.push(0);
memset(dist,-0x3f,sizeof dist);
dist[0]=0;
while(q.size())
{
int t=q.front();
q.pop();
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
dist[j]=max(dist[j],dist[t]+w[i]);
d[j]--;
if(d[j]==0)
{
q.push(j);
}
}
}
}
int main()
{
int n,m,c;
cin>>n>>m>>c;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
add(0,i,x);
d[i]++;
}
for(int i=1;i<=c;i++)
{
int a,b,x;
cin>>a>>b>>x;
add(a,b,x);
d[b]++;
}
topsort();
for(int i=1;i<=n;i++)
{
cout<<dist[i]<<endl;
}
return 0;
}
请问一下,为什么要找最长路呢
因为它需要满足所有条件,如果最短路,就可能会只满足一个最早的条件了。
满足所有条件,就需要满足时间最晚的条件,所以是最长路(个人理解,不喜勿喷)