其他的 OJ 可以通过这份代码,洛谷的在线 IDE 通过测试点 #1,但是洛谷评测全部 RE(Signal 11)。
不明白明明是一个 OJ 一个语言,为何会有这样的差别?玄关。
#include<bits/stdc++.h>
using namespace std;
vector<int> v[10005];
vector<int> t[10005];
vector<int> r[10005];
long long dis[10005];
int cnt[10005],n,m,s,e,now,a[10005],mint[1005][1005],minp[1005][1005];
bool isfind[10005];
queue<int> q,emp;
bool spfa(int st)
{
memset(dis,0x3f,sizeof(dis));
memset(cnt,0,sizeof(cnt));
memset(isfind,0,sizeof(isfind));
dis[st]=0;
isfind[st]=1;
q=emp;
q.push(st);
while(!q.empty())
{
int f=q.front();
//cout<<f<<endl;
q.pop();
isfind[f]=0;
for(int i = 0; i < v[f].size(); i++)
{
int nowv=v[f][i],nowt=t[f][i],nowr=r[f][i];
if (dis[nowt]>dis[f]+nowv||(dis[nowt]>=dis[f]+nowv&&cnt[nowt]>cnt[f]+nowr))
{
dis[nowt]=dis[f]+nowv;
cnt[nowt]=cnt[f]+nowr;
if (!isfind[nowt])
{
q.push(nowt);
isfind[nowt]=1;
}
}
}
}
}
int main()
{
memset(minp,0x3f,sizeof(minp));
memset(mint,0x3f,sizeof(mint));
cin>>s>>e>>n;
for(int i = 1; i <= n; i++)
{
int pr;
cin>>pr>>now;
for(int j = 1; j <= now; j++)
{
cin>>a[j];
}
for(int j = 1; j < now; j++)
{
for(int k = j+1; k <= now; k++)
{
m++;
t[a[j]].push_back(a[k]);
//t[a[k]].push_back(a[j]);
v[a[j]].push_back(pr);
//v[a[k]].push_back(pr);
r[a[j]].push_back(k-j);
//r[a[k]].push_back(k-j);
}
}
}
spfa(s);
// for(int i = 1; i <= 5; i++)
// {
// if(dis[i]>0x2f2f2f2f) cout<<2147483647<<" ";
// else cout<<dis[i]<<" ";
// }
// cout<<endl;
// for(int i = 1; i <= 5; i++)
// {
// if(cnt[i]>0x2f2f2f2f) cout<<2147483647<<" ";
// else cout<<cnt[i]<<" ";
// }
if(dis[e]>0x2f2f2f2f2f2f2f2f)
{
cout<<"-1 -1";
}
else
{
cout<<dis[e]<<" "<<cnt[e];
}
}