# 91 条题解

• @ 2016-06-01 19:45:17
``````#include <cstdio>
#include <algorithm>
#include <algorithm>
using namespace std;
const int MAXN = 300;
const int INF = 1000000;

int dis[MAXN][MAXN], a[MAXN];

int main()
{
int n, m, x, y, b;
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++)
scanf("%d", &a[i]);//第i个弯道时间
for(int i=1; i<=n; i++)
for(int j=i+1; j<=n; j++)
dis[i][j] = dis[j][i] = INF;
for(int i=1; i<=m; i++){
scanf("%d%d%d", &x, &y, &b);
dis[x][y] = min(dis[x][y], b);
}
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j] + a[k]);
int ans = INF;
for(int i=2; i<=n; i++)
ans = min(ans, dis[1][i] + a[i] + dis[i][1]);
if(ans == INF)  printf("-1");
else printf("%d", ans + a[1]);
return 0;
}
``````

floyd = AC

• @ 2019-02-11 14:23:25

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,s[201],a[201][201];
int main()
{
int i,j,k,x,y,b;
scanf("%d%d",&n,&m);
memset(a,0x3f,sizeof(a));
for(i=1;i<=n;i++)
scanf("%d",&s[i]);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&b);
if(b+s[y]<a[x][y])
a[x][y]=b+s[y];
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(a[i][j]>a[i][k]+a[k][j])
{
a[i][j]=a[i][k]+a[k][j];
}
}
if(a[1][1]==0x3f3f3f3f)
printf("-1");
else
printf("%d",a[1][1]);
return 0;
}

• @ 2018-07-15 21:13:36
``````//vijos p1423 最佳路线
//就是求经过点一的最小环(不过有点权)有向图
//时间复杂度最坏n^2*logn n=200
#include<bits/stdc++.h>
#define re register int
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
template<class T>inline bool sdf(T&x){
char c;register int y=1;while(c=getchar(),c<48||57<c)if(c=='-')y=-1;x=c^48;
while(c=getchar(),47<c&&c<58)x=(x<<1)+(x<<3)+(c^48);x*=y;
return true;
}
const int maxn=201;
int d[maxn];
int g[maxn][maxn];
bool vis[maxn];
int inf;
int n,m;
typedef pair<int,int> P;
int dijkstra(int start){
priority_queue <P,vector<P>,greater<P> > que;
memset(d,0x3f,sizeof(d));
d[start]=0;
que.push(P(0,start));
bool flag=0;
while(!que.empty()){
re u=que.top().second;
que.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=1;i<=n;i++){
if(i!=u){
if(d[i]>d[u]+g[u][i]+g[i][i]){
d[i]=d[u]+g[u][i]+g[i][i];
que.push(P(d[i],i));
}
}
}
if(!flag){
flag=1;
d[start]=inf;
vis[start]=0;
}
}
return d[start];
}
int main(){
sdf(n),sdf(m);
int x,y,z;
memset(g,0x3f,sizeof(g));
inf=g[0][0];
for(re i=1;i<=n;i++) sdf(g[i][i]);
for(re i=1;i<=m;i++)
{
sdf(x),sdf(y),sdf(z);
g[x][y]=min(g[x][y],z);
}
int ans=dijkstra(1);
if(ans==inf) puts("-1");
else printf("%d",ans);
}
``````
• @ 2018-07-15 21:15:37

跑得飞快
#1 Accepted 2ms 504.0 KiB
#2 Accepted 2ms 500.0 KiB
#3 Accepted 3ms 408.0 KiB
#4 Accepted 2ms 500.0 KiB
#5 Accepted 3ms 512.0 KiB
#6 Accepted 2ms 496.0 KiB
#7 Accepted 11ms 512.0 KiB
#8 Accepted 3ms 492.0 KiB
#9 Accepted 5ms 484.0 KiB
#10 Accepted 16ms 512.0 KiB

• @ 2019-02-11 14:22:45

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,s[201],a[201][201];
int main()
{
int i,j,k,x,y,b;
scanf("%d%d",&n,&m);
memset(a,0x3f,sizeof(a));
for(i=1;i<=n;i++)
scanf("%d",&s[i]);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&b);
if(b+s[y]<a[x][y])
a[x][y]=b+s[y];
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(a[i][j]>a[i][k]+a[k][j])
{
a[i][j]=a[i][k]+a[k][j];
}
}
if(a[1][1]==0x3f3f3f3f)
printf("-1");
else
printf("%d",a[1][1]);
return 0;
}

• @ 2016-12-28 21:45:20

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 752 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 752 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 752 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 752 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 752 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 752 KiB, score = 10
测试数据 #6: Accepted, time = 109 ms, mem = 756 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 756 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 752 KiB, score = 10
测试数据 #9: Accepted, time = 109 ms, mem = 752 KiB, score = 10
Accepted, time = 248 ms, mem = 756 KiB, score = 100

先用floyd过一次再想想怎么用dijkstra。。。

代码
```c++
#include<iostream>
#include<iomanip>
#include<cstring>
#include<vector>
#include<sstream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<math.h>
#include<map>
#include<cctype>
#include<queue>
#include<functional>
#include<set>
#define Mem(a,b) memset((a),(b),sizeof((a)))
#define Sy system("pause")
#define For(a,b) for(int i = (a);i<(b);i+=1)
const int maxn = 220;
const int INF = 0x3f3f3f;
using namespace std;
int d[maxn], G[maxn][maxn];
int ans = INF;
int main(){
For(0, maxn){
d[i] = INF;
for (int j = 0; j < maxn; j += 1) G[i][j] = i == j ? 0 : INF;
}
int n, m, a, b, c;
scanf("%d %d", &n, &m);
For(1, n + 1) scanf("%d", &d[i]);
For(1, m + 1){
scanf("%d %d %d", &a, &b, &c);
G[a][b] = min(G[a][b], c);
}

for (int k = 1; k <= n; k += 1)
for (int i = 1; i <= n; i += 1)
for (int j = 1; j <= n; j += 1){
G[i][j] = min(G[i][j], G[i][k] + G[k][j] + d[k]);
}

For(2, n + 1){
ans = min(ans, G[1][i] + G[i][1] + d[i]);
}
if (ans != INF)
printf("%d\n", ans + d[1]);
else
printf("-1\n");
//Sy;
return 0;
}
```

• @ 2016-08-25 07:53:53

SPFA
#include"iostream"

#include"cstring"

#include"math.h"
#include"cstdio"
#include"map"
#include"set"
#include"algorithm"
#include"vector"
#include"queue"

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int INF=110000000; //最大边数*最大边长+10
const int maxn=200+10;//最大点数
int a[maxn];
struct edge //边
{
int from,to,dist;edge(int u,int v,int w){from=u;to=v;dist=w;}
};
struct node
{
int d;int u;
node(){}
node(int dd,int uu){d=dd;u=uu;}
friend bool operator < (node a,node b){return a.d>b.d;}
};
struct dijkstra
{

int n,m;
vector<edge>edges;
vector<int>g[maxn];

int visit[maxn]; //dijkstra

int cnt[maxn]; //SPFA
int inq[maxn];

int d[maxn];
int p[maxn];

void init(int n){this->n=n;for(int i=0;i<n;i++)g[i].clear();edges.clear();}
void add_edge(int u,int v,int w){edges.push_back(edge(u,v,w));int m=edges.size();g[u].push_back(m-1);} //加入一条边 无向图要加两次

void djk(int s)
{
priority_queue<pii,vector<pii>,greater<pii> >Q;
memset(visit,0,sizeof(visit));
for(int i=0;i<n;i++) d[i]=INF;
d[s]=a[s];
Q.push(make_pair(d[s],s));
while(!Q.empty())
{
pii x=Q.top();Q.pop();
int u=x.second;
visit[u]=1;
for(int i=0;i<g[u].size();i++)
{
edge& e=edges[g[u][i]];
if(!visit[e.to])
if(d[e.to]>d[e.from]+e.dist+a[e.to])
{
d[e.to]=d[e.from]+e.dist+a[e.to];
p[e.to]=g[u][i];
Q.push(make_pair(d[e.to],e.to));
}
}
}

}
int SPFA(int s)
{
queue<int>Q;
memset(inq,0,sizeof(inq));
memset(cnt,0,sizeof(cnt));
for(int i=0;i<n;i++) d[i]=INF;
d[s]=a[s];
Q.push(s);
inq[s]=1;cnt[s]=1;
while(!Q.empty())
{
int u=Q.front();Q.pop();
inq[u]=0;
for(int i=0;i<g[u].size();i++)
{
edge &e=edges[g[u][i]];

if(d[e.from]<INF&&d[e.to]>d[e.from]+e.dist+a[e.to]) //松弛
{
d[e.to]=d[e.from]+e.dist+a[e.to];

if(!inq[e.to]) //不在队列中才能入队
{
Q.push(e.to);
inq[e.to]=1;cnt[e.to]++;
if(cnt[e.to]>n) return 0;
}
}
}
}
return 1;
}
};

int main()
{

int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
int i,j,k;
for(i=0;i<n;i++)
scanf("%d",&a[i]);
dijkstra b,c;
b.init(n);c.init(n);
for(i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
}
int Min=INF;
b.SPFA(0);
for(i=1;i<n;i++)
{
c.SPFA(i);
Min=min(b.d[i]+c.d[0]-a[0]-a[i],Min);
}
if(Min==INF) puts("-1");
else printf("%d\n",Min);

}
return 0;
}

• @ 2016-08-25 07:25:34

楼下说的正反遍历我没实现成功，但是正向遍历一遍然后枚举另一个点是可以的。
Dijkstra
#include"iostream"
#include"cstring"
#include"math.h"
#include"cstdio"
#include"map"
#include"set"
#include"algorithm"
#include"vector"
#include"queue"

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int INF=110000000; //最大边数*最大边长+10
const int maxn=200+10;//最大点数
int a[maxn];
struct edge //边
{
int from,to,dist;edge(int u,int v,int w){from=u;to=v;dist=w;}
};
struct node
{
int d;int u;
node(){}
node(int dd,int uu){d=dd;u=uu;}
friend bool operator < (node a,node b){return a.d>b.d;}
};
struct dijkstra
{

int n,m;
vector<edge>edges;
vector<int>g[maxn];
int visit[maxn];
int d[maxn];
int p[maxn];

void init(int n){this->n=n;for(int i=0;i<n;i++)g[i].clear();edges.clear();}
void add_edge(int u,int v,int w){edges.push_back(edge(u,v,w));int m=edges.size();g[u].push_back(m-1);} //加入一条边 无向图要加两次

void djk(int s)
{
priority_queue<pii,vector<pii>,greater<pii> >Q;
memset(visit,0,sizeof(visit));
for(int i=0;i<n;i++) d[i]=INF;
d[s]=a[s];
Q.push(make_pair(d[s],s));
while(!Q.empty())
{
pii x=Q.top();Q.pop();
int u=x.second;
visit[u]=1;
for(int i=0;i<g[u].size();i++)
{
edge& e=edges[g[u][i]];
if(!visit[e.to])
if(d[e.to]>d[e.from]+e.dist+a[e.to])
{
d[e.to]=d[e.from]+e.dist+a[e.to];
p[e.to]=g[u][i];
Q.push(make_pair(d[e.to],e.to));
}
}
}

}

};

int main()
{

int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
int i,j,k;
for(i=0;i<n;i++)
scanf("%d",&a[i]);
dijkstra b,c;
b.init(n);c.init(n);
for(i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
}
int Min=INF;
b.djk(0);
for(i=1;i<n;i++)
{
c.djk(i);
Min=min(b.d[i]+c.d[0]-a[0]-a[i],Min);
}

/*
int Min=INF;
for(i=1;i<n;i++)
{
b.djk(0);c.djk(i);
Min=min(Min,b.d[i]+c.d[0]-a[i]-a[0]);
}
*/
if(Min==INF) puts("-1");
else printf("%d\n",Min);

}
return 0;
}

• @ 2016-08-14 11:30:53

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 720 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 720 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 720 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 720 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 724 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 720 KiB, score = 10
测试数据 #6: Accepted, time = 375 ms, mem = 720 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 716 KiB, score = 10
测试数据 #8: Accepted, time = 46 ms, mem = 720 KiB, score = 10
测试数据 #9: Accepted, time = 312 ms, mem = 724 KiB, score = 10
Accepted, time = 809 ms, mem = 724 KiB, score = 100

/*
引用楼下wang...yanheng大神的话：
对于此题而言，floyd可以做，但不是最优选择。如果把数据加强到n=1000，
则应该使用两次Dijkstra（正向反向各一次），然后枚举中间点来选取答案。
这样做的时间复杂度为O(V2)O(V2)，对于n=1000绰绰有余。

Floyd做法：a[i]表示第i个弯道时间，d[i][j]表示第i个弯道到第j个弯道时间，初始化INF
接着运用floyd求出各个弯道之间直道最短时间，记得要加上连接弯道的直道时间。
题目要求要经过1弯道的最短路且必要有一直道路，说明必要有两个弯道连接而成加上直道，
则枚举2到n所有点，取其d[1][i]+a[i]+d[i][1]+a[1]最小值。
还需要判断是否存在解即判断与INF的关系。
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int INF=0x7ffffff;
int d[202][202];
int a[202];
int n,m;

int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j) d[i][j]=INF;
for(int i=1;i<=m;i++)
{
int x,y,v;
cin>>x>>y>>v;
d[x][y]=min(d[x][y],v);
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k]+a[k]+d[k][j]);
int ans=INF;
for(int i=2;i<=n;i++)
ans=min(ans,d[1][i]+a[i]+d[i][1]+a[1]);
if(ans==INF)
cout<<"-1"<<endl;
else
cout<<ans<<endl;
return 0;
}

• @ 2016-07-29 21:02:32

对于此题而言，floyd可以做，但不是最优选择。如果把数据加强到n=1000，则应该使用两次Dijkstra（正向反向各一次），然后枚举中间点来选取答案。这样做的时间复杂度为`\(O(V^2)\)`，对于n=1000绰绰有余。

• @ 2016-01-30 19:20:24

求第6组数据！！！

• @ 2015-08-04 19:24:52

program p1423;
var a:array[1..200,1..200] of longint;
w:array[1..200] of longint;
i,j,k,l,m,n,r,q,p:longint;
begin
for i:=1 to n do
for j:=1 to n do a[i,j]:=10000000;
for i:=1 to n do readln(w[i]);
for i:=1 to m do
if r+w[q]<a[p,q] then a[p,q]:=r+w[q];
end;
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if a[i,j]>a[i,k]+a[k,j] then
a[i,j]:=a[i,k]+a[k,j];
if a[1,1]=10000000 then a[1,1]:=-1;
writeln(a[1,1]);
end.

• @ 2015-07-07 00:53:42

P1423最佳路线
Accepted

记录信息

评测状态 Accepted
题目 P1423 最佳路线
递交时间 2015-07-07 00:53:14
代码语言 C++
评测机 VijosEx
消耗时间 294 ms
消耗内存 440 KiB
评测时间 2015-07-07 00:53:17

评测结果

编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 436 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 440 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 436 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 440 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 440 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 436 KiB, score = 10

测试数据 #6: Accepted, time = 109 ms, mem = 436 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 440 KiB, score = 10

测试数据 #8: Accepted, time = 46 ms, mem = 436 KiB, score = 10

测试数据 #9: Accepted, time = 109 ms, mem = 436 KiB, score = 10

Accepted, time = 294 ms, mem = 440 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>

using namespace std;

int n , m;
int i , j , k;
int a[200 + 2];
int g[200 + 2][200 + 2];
int x , y , w;
int mind;

int min( int a , int b )
{
if( a > b )
return b;
return a;
}

int main()
{
scanf( "%d %d" , &n , &m );
for( i = 1 ; i <= n ; i++ )
scanf( "%d" , &a[i] );
for( i = 1 ; i <= n ; i++ )
for( j = 1 ; j <= n ; j++ )
g[i][j] = 10000000;
for( i = 1 ; i <= n ; i++ )
g[i][i] = 0;
for( i = 0 ; i < m ; i++ )
{
scanf( "%d %d %d" , &x , &y , &w );
g[x][y] = min( g[x][y] , w );
}
for( k = 1 ; k <= n ; k++ )
for( i = 1 ; i <= n ; i++ )
for( j = 1 ; j <= n ; j++ )
g[i][j] = min( g[i][j] , g[i][k] + g[k][j] + a[k] );
int mind = 10000000;
for( k = 2 ; k <= n ; k++ )
mind = min( mind , g[1][k] + g[k][1] + a[k] + a[1] );
if( mind != 10000000 )
cout << mind << endl;
else
cout << -1 << endl;
return 0;
}

• @ 2015-05-20 15:53:04

SO EASy！！！
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int w[201][201],a[201],f[201];
queue <int>que;
int n,m;
int main()
{
int x,y,z,ans=5555555;
//freopen("P1423.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
if(w[x][y]==0||w[x][y]>z)
w[x][y]=z;
}
memset(f,100,sizeof(f));
que.push(1);
f[1]=0;
int k;
while(que.size()!=0)
{
k=que.front();
que.pop();
for(int i=1;i<=n;i++)
if(w[k][i]>0&&(f[i]>f[k]+w[k][i]+a[i]||f[i]==0))
{
f[i]=f[k]+w[k][i]+a[i];
if(i==1&&(ans==0||ans>f[i]))
ans=f[i];
else
que.push(i);
}
}
if(ans==5555555)
{
printf("-1");
return 0;
}
printf("%d",ans);
return 0;

}

• @ 2014-03-29 09:05:47

var dist,time:array[0..201] of longint;
map:array[0..201,0..201] of longint;
i,ans,n,m,j,a,b,c:longint;
function min(x,y:longint):longint;
begin
if x<y then exit(x) else exit(y);
end;
procedure spfa;
var h,t,x:longint;
vis:array[0..201] of boolean;
q:array[0..201] of longint;
begin
fillchar(vis,sizeof(vis),false);
fillchar(q,sizeof(q),0);
h:=0;t:=1;q[1]:=1;vis[1]:=true;dist[1]:=time[1];
while h<>t do
begin
h:=h mod n+1;
x:=q[h];
vis[x]:=false;
for i:=1 to n do
if (map[x,i]<>maxlongint shr 1) and (dist[x]+map[x,i]+time[i]<dist[i]) then
begin
dist[i]:=dist[x]+map[x,i]+time[i];
if not(vis[i]) then
begin
t:=t mod n+1;
q[t]:=i;
vis[i]:=true;
end;
end;
end;
end;
begin
for i:=1 to n do
for j:=1 to n do
map[i,j]:=maxlongint shr 1;
for i:=1 to n do readln(time[i]);
for i:=1 to m do
begin
map[a,b]:=min(map[a,b],c);
end;
for i:=1 to n do dist[i]:=maxlongint shr 1;
spfa;
ans:=maxlongint;
for i:=2 to n do ans:=min(ans,dist[i]+map[i,1]);
if ans>maxlongint shr 1 then writeln('-1') else writeln(ans);
end.
直接SPFA！

• @ 2013-09-30 19:18:43

对这个测评机彻底无语，0秒超时，0.2秒反而ac

• @ 2012-09-27 20:47:18

各位大牛，帮忙看看这个怎么只能过9个点，最后一个过不了

const maxn=100000000;

var w:array[1..200] of longint;

q,d:array[1..200] of longint;

mark:array[1..200] of boolean;

a,b:array[1..200,0..200] of longint;

n,m,x,y,z,min:longint;

i,j,h,t,p:longint;

begin

fillchar(w,sizeof(w),0);

fillchar(b,sizeof(b),0);

fillchar(a,sizeof(a),0);

for i:=1 to n do

for i:=1 to m do

begin

if a[x,y]>0 then

if z+w[y]0 then

begin

inc(b);

b[i,b]:=j;

end;

fillchar(q,sizeof(q),0);

fillchar(mark,sizeof(mark),false);

for i:=2 to n do

d[i]:=maxn;

h:=0;

t:=1;

q[1]:=1;

mark[1]:=true;

d[1]:=0;

while ht do

begin

h:=(h mod n)+1;

p:=h;

mark[p]:=false;

for i:=1 to b[p,0] do

if d[p]+a[p,b[p,i]]

• @ 2012-09-24 20:01:34

├ 测试数据 01：答案正确... (0ms, 1216KB)

├ 测试数据 02：答案正确... (0ms, 1216KB)

├ 测试数据 03：答案正确... (0ms, 1216KB)

├ 测试数据 04：答案正确... (0ms, 1216KB)

├ 测试数据 05：答案正确... (0ms, 1216KB)

├ 测试数据 06：答案正确... (0ms, 1216KB)

├ 测试数据 07：答案正确... (0ms, 1216KB)

├ 测试数据 08：答案正确... (0ms, 1216KB)

├ 测试数据 09：答案正确... (0ms, 1216KB)

├ 测试数据 10：答案正确... (0ms, 1216KB)

每个弯道拆成两个点，然后spfa

• @ 2009-11-07 09:54:44

。。跳楼算了。这种水题交了5遍。

看到那爆小的数据范围，有种想用Floyd的冲动。

但抱着对Spfa的热爱，用了Spfa。

看到那爆小的数据范围，心血来潮，把使用多年的邻接表改成邻接矩阵。

结果。重边的判断错了N次.杯具啊。。。

（邻接表是不用判重边的I.I）

• @ 2009-11-03 21:39:44

Accepted 有效得分：100 有效耗时：0ms

把读入的右边的1当成n+1,求1-n+1的最短路就行了额..注意重边哦~~

• @ 2009-10-31 01:16:57

30分/80分的同志们注意下。。fillchar(127)是会挂的。。建议改成for。。g初始=10^7刚好。。

ID
1423

5

1849

586

32%

2