题目描述
blablabla
样例
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N =5010,M=2e5+10;
int h[N],e[M],ne[M],w[M],idx;
int d1[N],d2[N];
bool st1[N],st2[N];
int n,m;
void add(int a,int b,int c)
{
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx;
}
int spfa1(int x)
{
memset(d1,0x3f,sizeof d1);
d1[x]=0;
st1[x]=true;
queue[HTML_REMOVED]q;
q.push(x);
while(q.size())
{
int t=q.front();
q.pop();
st1[t]=false;
for(int i=h[t];~i;i=ne[i])
{
int j=e[i];
if(d1[j]>d1[t]+w[i])
{
d1[j]=d1[t]+w[i];
if(!st1[j])
{
q.push(j);
st1[j]=true;
}
}
}
}
}
int spfa2(int x)
{
memset(d2,0x3f,sizeof d2);
d2[x]=0;
st2[x]=true;
queue[HTML_REMOVED]q;
q.push(x);
while(q.size())
{
int t=q.front();
q.pop();
st2[t]=false;
for(int i=h[t];~i;i=ne[i])
{
int j=e[i];
if(d2[j]>d2[t]+w[i])
{
d2[j]=d2[t]+w[i];
if(!st2[j])
{
q.push(j);
st2[j]=true;
}
}
}
}
}
int main()
{
memset(h,-1,sizeof h);
cin>>n>>m;
while(m–)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
spfa1(1);
spfa2(n);
int ans=0x3f3f3f3f;
for(int i=1;i<=n;i)
{
for(int j=h[i];~j;j=ne[j])
{
int t=e[j];
//cout<[HTML_REMOVED]t w[j]
int temp=d1[i]+d2[t]+w[j];
if(temp>d1[n]&&temp<ans)
{
ans=temp;
}
}
}
cout<<ans;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla