88 条题解

• @ 2019-09-12 15:56:30

Dijkstra
记录每次选中点的上一个路径源，从终点向前遍历，找到路径。

``````#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

int n;
int ma[1001][1001]={0};

int dis[1001];
int last[1001]={0};
bool vis[1001]={0};

int main()
{
cin>>n;
int i,j,ans,now,next;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cin>>ma[i][j];
}
}
vis[1]=true;
memset(dis,62,sizeof(dis));
dis[1]=0;
now=1;
while(now!=n)
{
ans=1e9;
for(i=1;i<=n;i++)
{
if(ma[now][i]>0&&!vis[i])
{
if(dis[i]>dis[now]+ma[now][i])
{
dis[i]=dis[now]+ma[now][i];
last[i]=now;
}
}
if(ans>dis[i]&&!vis[i])
{
ans=dis[i];
next=i;
}
}
vis[next]=true;
now=next;
}
vector<int> vi;
now=n;
vi.push_back(now);
while(now!=1)
{
now=last[now];
vi.push_back(now);
}
for(i=vi.size()-1;i>=0;i--)
{
cout<<vi[i]<<' ';
}
cout<<endl;
cout<<ans<<endl;
return 0;
}
``````
• @ 2019-04-18 10:03:20

#include <iostream>
using namespace std;
#include <stack>
#define INFT 0x232323
#define WHITE 0
#define BLACK 1
#define GRAY -1

int visited[10001];
int G[10001][10001];
int parent[10001];
int d[10001];
int N;

void initial()
{
for (int i = 0; i < 10001; i++)
{
d[i] = INFT;
parent[i] = -1;
visited[i] = 0;
}

}

void Djkar(int s, int e)
{
d[s] = 0;

while (1)
{
int minv = INFT;
int choice = -1;

for (int i = 1; i <= N; i++)
{
if (visited[i] != BLACK && d[i] < minv)
{
minv = d[i];
choice = i;
}
}

if (choice == -1)
break;

visited[choice] = BLACK;

for (int i = 1; i <= N; i++)
{
if (visited[i] != BLACK && G[choice][i] != INFT)
{
if (G[choice][i] + d[choice] < d[i])
{
d[i] = G[choice][i] + d[choice];
parent[i] = choice;
visited[i] = GRAY;
}
}
}
}
stack<int> ss;

int po = e;

ss.push(po);

while (parent[po] != -1)
{
ss.push(parent[po]);
po = parent[po];
}

cout << ss.top();
ss.pop();

while (!ss.empty())
{
cout << " " << ss.top();
ss.pop();
}
cout << endl;
cout << d[e];
}

int main()
{
cin >> N;
initial();

for(int i=1;i<=N;i++)
for (int j = 1; j <= N; j++)
{
int tmp;
cin >> tmp;
if (tmp)
{
G[i][j] = tmp;
}
else
{
G[i][j] = INFT;
}
}

Djkar(1, N);
r****

• @ 2018-02-08 09:56:55

迪杰特斯拉嘻嘻 记录路线的有一点点麻烦（也许是我太菜）
```cpp
#include<stdio.h>
const int maxn=110,INF=1<<29;
long long int mp[1100][1100],dis[1100],v[1100],lu[1100];
int main() {
int n;
scanf("%d",&n);
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
scanf("%d",&mp[i][j]);
if(!mp[i][j])mp[i][j]=INF;
}
}
for(int i=1; i<=n; i++) {
dis[i]=mp[1][i];
}
v[1]=1;
int k=0;
for(int i=1;i<=n;i++)lu[i]=1;
int flag=1;
for(int i=1; i<=n; i++) {
int minn=INF;
int p;
for(int j=1; j<=n; j++) {
if(!v[j]&&dis[j]<minn) {
minn=dis[j];
p=j;
}
}
v[p]=1;
if(flag){
lu[p]=1;//经过第一个p的最短路是来自起点1的
flag=0;
}
for(int j=1; j<=n; j++) {
if(dis[p]+mp[p][j]<dis[j]) {
dis[j]=dis[p]+mp[p][j];
lu[j]=p;//到j点的最短路是来自于p的 ->到终点的最短路是来自于上一个p的
}
}

}
int swap[1100]={0};
k=0;
for (int i=n;i>1;i=lu[i]) swap[k++]=lu[i];//lu数组中记录的是倒着的 而且不包含终点 所以交换一下
for(int i=k-1;i>=0;i--)printf("%d ",swap[i]);
printf("%d\n",n);
printf("%d\n",dis[n]);
}
```

• @ 2017-11-06 16:52:51

dijkstra来一波
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=10000000;
int n,m,p,t;
int g[1008][1008],pre[1008],c[1008],pree[1008];
bool b[1008];
void dijkstra()
{
for(int i=1;i<=n;i++)
{
int minl=M,k=0;
for(int j=1;j<=n;j++)
if(!b[j]&&minl>c[j])
{
minl=c[j];
k=j;
}
if(k==0) break;
b[k]=true;
for(int j=1;j<=n;j++)
if(c[k]+g[k][j]<c[j])
{
pre[j]=k;
c[j]=c[k]+g[k][j];
}
}
return;
}
void outans(int a)
{
if(a==1) return;
outans(pre[a]);
cout<<" "<<a;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>g[i][j];
if(g[i][j]==0) g[i][j]=M;
}
for(int i=1;i<=n;i++)
{c[i]=g[1][i]; pre[i]=1;}
b[1]=true; c[1]=0;
dijkstra();
cout<<1;
outans(n);
cout<<endl<<c[n];
return 0;
}

• @ 2017-10-26 20:57:18

来个Dijkstra

``````#include<algorithm>
#include <iostream>
#include  <cstring>
#include   <cstdio>
#include    <cmath>
using namespace std;
const int MAXN = 1001;
const int INF  = 99999999;
#define For(i, a, b) for(int i=a; i<=b; i++)
#define Dow(i, a, b) for(int i=a; i>=b; i--)

int n, map[MAXN][MAXN];
int dis[MAXN], pre[MAXN];
bool vis[MAXN];

inline void init() {
For(i, 1, n) For(j, 1, n) {
scanf("%d", &map[i][j]);
if(!map[i][j]) map[i][j] = INF;
}
}

inline void Dijkstra(int s) {
memset(vis, false, sizeof(vis));
vis[s] = true;
For(i, 1, n) {
dis[i] = map[s][i];
pre[i] = s;
}
int Min_val, Min_pos;
For(i, 2, n) {
Min_val = INF;
For(j, 1, n)
if(!vis[j] && dis[j]<Min_val) {
Min_val = dis[j];
Min_pos = j;
}
vis[Min_pos] = true;
For(j, 1, n) {
if(!vis[j] && map[Min_pos][j]+Min_val<dis[j]) {
dis[j] = map[Min_pos][j]+Min_val;
pre[j] = Min_pos;
}
}
}
}

void print(int x) {
if(x == 1) return ;
print(pre[x]);
printf("%d ", x);
}

int main() {

init();
Dijkstra(1);
printf("%d ", 1); print(n);
printf("\n%d", dis[n]);

return 0;
}

bool fg=1; char ch;
ch = getchar();
if(ch == '-') { fg=-1; printf("-"); ch = getchar(); }
while(ch>='0' && ch<='9') {
x = (x<<3) + (x<<1) + ch - 48;
ch = getchar();
}
x *= fg;
}

``````
• @ 2017-10-02 00:30:34
``````var
a,w:array[-1..10000,-1..10000] of longint;
p,d,pre:array[-1..10000] of longint;
f:array[-1..10000] of boolean;
i,j,n,xx,yy,t,tt:longint;

procedure spfa(v:longint);
var
i,x:longint;
begin
fillchar(d,sizeof(d),\$7f);
fillchar(f,sizeof(f),false);
d[v]:=0; t:=0; tt:=1; p[1]:=v; f[v]:=true;
while t<=tt do
begin
t:=t+1;
x:=p[t];
f[x]:=false;
for i:=1 to a[x,-1] do
if d[a[x,i]]>d[x]+w[x,a[x,i]] then
begin
d[a[x,i]]:=d[x]+w[x,a[x,i]];
pre[a[x,i]]:=x;
if not(f[a[x,i]]) then
begin tt:=tt+1; p[tt]:=a[x,i]; f[a[x,i]]:=true; end;
end;
end;
end;

procedure pp(v:longint);
begin
if v=1 then write(v,' ')
else
begin
pp(pre[v]);
write(v,' ');
end;
end;

begin
for i:=1 to n do
for j:=1 to n do
begin
if w[i,j]>0 then
begin
inc(a[i,-1]);
a[i,a[i,-1]]:=j;
end;
end;
spfa(1);
pp(n);
writeln;
write(d[n]);
end.
``````
• @ 2017-08-04 20:41:05

Pascal版SPFA

``````const INF=maxlongint div 3;
type
rel=array[0..100001] of longint;
var
a:array[1..1001,1..1001] of longint;
way:rel;
i,j,n,m,x,y,p,q,c,ans:longint;

function exist(w:rel; l,r,x:longint):boolean;
var i:longint;
begin
for i:=l to r-1 do
if w[i]=x then exit(true);
exit(false);
end;

function spfa(x,y:longint):longint;
var
dis,pre,v:rel;
i,j,l,r:longint;
begin

//spfa

fillchar(v,sizeof(v),0);
for i:=1 to n do dis[i]:=INF; dis[x]:=0;
l:=1; r:=2; v[1]:=x;
while l<r do begin
for i:=1 to n do
if (a[v[l],i]<>INF) and (a[v[l],i]<>0) then
if dis[v[l]]+a[v[l],i]<dis[i] then begin
dis[i]:=dis[v[l]]+a[v[l],i];
pre[i]:=v[l];
if not exist(v,l,r,i) then begin
v[r]:=i;
inc(r);
end;
end;
inc(l);
end;

//print

i:=n; j:=1;
while i>0 do begin way[j]:=i; inc(j); i:=pre[i]; end;
way[0]:=j-1;

exit(dis[y]);
end;

begin
for i:=1 to n do
for j:=1 to n do
for i:=1 to n do
for j:=1 to n do
if (i<>j) and (a[i,j]=0) then a[i,j]:=INF;
ans:=spfa(1,n);
for i:=way[0] downto 1 do write(way[i],' ');
writeln;
writeln(ans);
end.

``````
• @ 2017-06-24 16:51:08
``````//弱弱的floyd， 膜楼下大神
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000000000;
int dis[1005][1005];
int path[1005][1005];
int main()
{
int num;
scanf("%d", &num);
for(int i = 1; i <= num; i++)
for(int k = 1; k <= num; k++)
{
scanf("%d", & dis[i][k]);
if(dis[i][k] == 0)
dis[i][k] = MAX;
path[i][k] = k;
}
for(int k = 1; k <= num; k++)
for(int i = 1; i <= num; i++)
for(int j = 1; j <= num; j++)
if(dis[i][j] > dis[i][k] + dis[k][j])
{
dis[i][j] = dis[i][k] + dis[k][j];
path[i][j] = path[i][k];
}
int st = 1, en = num;
while(st != en)
{
printf("%d ", st);
st = path[st][en];
}
printf("%d\n", en);
printf("%d\n", dis[1][num]);
return 0;
}
``````
• @ 2017-10-27 14:50:18

真的服你这个Floyed后继，卡点过，我用的Floyed前驱，TE了……

• @ 2017-11-05 22:24:12

过不去，害我wr了8次，赔我

• @ 2016-09-07 13:41:02

裸地SPFA。。
不过就如楼下所说，数组开大点(╯3╰)。。。

代码
```c++ #include<algorithm> #include<cstdio> #include<cstring> #include<iostream> #include<queue> #define MAXV 2002 #define MAXE 50010 #define LL long long using namespace std; int T,n,m,u,v; bool vis[MAXV]; LL dis[MAXV]={6000}; long path[MAXV]={0},path1[MAXV]={0}; struct Node { int to,next,w; }; Node edge[MAXE]; int idx,head[MAXV]; void init() { idx=1; memset(head,0,sizeof(head)); } void addEdge(int u,int v,int w) { edge[idx].to=v; edge[idx].w=w; edge[idx].next=head[u]; head[u]=idx; idx++; } void visit(int sta) { for(int i=1;i<=n;i++) { vis[i]=0; dis[i]=6000; } queue<int>Q; Q.push(sta); vis[sta]=1; dis[sta]=0; while(!Q.empty()) { int now=Q.front(); Q.pop(); vis[now]=0; for(int i=head[now];i;i=edge[i].next) { int w=edge[i].w; int son=edge[i].to; if(dis[now]+w<dis[son]) { dis[son]=dis[now]+w; path[son]=now;//路径记录 if(!vis[son]) { Q.push(son); // 子节点未访问过 vis[son]=1; // 标记已访问 } } } } else { int k=n; for (int i=n;i>0;i--) { path1[i]=path[k]; k=path[k]; } for(int i=1;i<=n;i++) if (path1[i]!=0) cout<<path1[i]<<" "; cout<<n<<endl<<dis[n]<<endl; }//麻烦的路径还原。。请恕我愚昧 } int main() { init(); scanf("%d",&n); if (m==0 && n==0) { return 0; } for(int i=1;i<=n;i++) for (int j=1;j<=n;j++) { int w; scanf("%d",&w); if (w != 0) addEdge(i,j,w); } visit(1); return 0; } ```

• @ 2016-08-10 18:33:13

数组开小了就太坑了！！害得我RE四次
```c++ #include <cstdio> #include <cstring> #include <iostream> using namespace std; int first[1005]; struct edge{ int point,next,len; } e[800005]; int dis[1005], path[1005]; int n; void add(int i, int u, int v, int w){ e[i].point = v; e[i].next = first[u]; e[i].len = w; first[u] = i; } void printpath(int k){ if (path[k]!=0) printpath(path[k]); printf("%d ",k); } void spfa(int s){ for (int j = first[s]; j; j = e[j].next) { if (dis[e[j].point]>dis[s]+e[j].len){ dis[e[j].point]=dis[s]+e[j].len; path[e[j].point]=s; spfa(e[j].point); } } } int main(){ int x, now=0; scanf("%d",&n); for(int i=1; i<=n; i++) for (int j=1;j<=n;j++){ scanf("%d",&x); if (x!=0) add(++now,i,j,x); } memset(dis,0x3f,sizeof(dis)); dis[1]=0; spfa(1); printpath(n); printf("\n%d",dis[n]); return 0; } ```

• @ 2016-05-06 18:10:40

裸的SPFA

``````#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
const int inf = 1<<30;
int n;
int d[1100];
int f[1100];
bool in[1100];
struct edge {
int to;
int val;
edge (int a, int b) : to(a), val(b) {}
};
vector<edge> g[1100];
queue<int> q;
stack<int> ans;
int main ()
{
//freopen ("in.txt", "r", stdin);
cin >> n;
int temp;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
cin >> temp;
if (temp) g[i].push_back(edge(j, temp));
}
for (int i = 1; i <= n; i++) d[i] = inf;
d[1] = 0;
in[1] = true;
q.push(1);
while (!q.empty()) {
temp = q.front();
q.pop();
in[temp] = false;
for (int i = 0; i < g[temp].size(); i++) {
if (d[g[temp][i].to] > d[temp] + g[temp][i].val) {
d[g[temp][i].to] = d[temp] + g[temp][i].val;
f[g[temp][i].to] = temp;
if (!in[g[temp][i].to]) q.push(g[temp][i].to);
}
}
}
int p = n;
while (p != 1) {
ans.push(p);
p = f[p];
}
cout << 1;
while (!ans.empty()) {
p = ans.top();
ans.pop();
cout << " " << p;
}
cout << endl << d[n];
return 0;
}
``````
• @ 2015-11-04 13:17:30

此题数据太弱。上次手贱将运算符重载打错，小根堆变成大根堆居然还能AC。
Dijkstra算法加STL priority_queue，使用邻接表存储。
##Block Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <queue>
#define rep(i,l,r) for (int i=l; i<=r; i++)
#define clr(x,y) memset(x,y,sizeof(x))
#define travel(x) for (int i=last[x]; i; i=edge[i].pre)
typedef long long ll;
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1010;
struct Edge{
int pre,to,cost;
}edge[1000000];
struct node{
int dis,val;
node(int x,int y){
val = x; dis = y;
}
inline bool operator < (const node &p) const{
return val > p.val;
}
};
int n,z,temp,tot=0,top=0,d[maxn],last[maxn],pre[maxn],route[maxn];
int ans = 0, f = 1;
char c = getchar();
while (!isdigit(c)){
if (c== '-') f = -1;
c = getchar();
}
while (isdigit(c)){
ans = ans * 10 + c - '0';
c = getchar();
}
return ans * f;
}
inline void addedge(int x,int y,int z){
edge[++tot].pre = last[x];
edge[tot].to = y;
edge[tot].cost = z;
last[x] = tot;
}
void dijk(){
priority_queue <node> q;
clr(d,INF); d[1] = 0;
q.push(node(1,0));
while(!q.empty()){
node now = q.top();
q.pop();
if (d[now.val] != now.dis) continue;
travel(now.val){
if (d[edge[i].to] > d[now.val] + edge[i].cost){
d[edge[i].to] = d[now.val] + edge[i].cost;
pre[edge[i].to] = now.val;
q.push(node(edge[i].to,d[edge[i].to]));
}
}
}
}
int main(){
rep(i,1,n) rep(j,1,n){
}
dijk(); temp = n;
while(temp){
route[++top] = temp;
temp = pre[temp];
}
for(int i=top; i>=2; i--) printf("%d ",route[i]);
printf("%d\n",route[1]);
printf("%d\n",d[n]);
return 0;
}

• @ 2015-10-18 20:01:16

大众，我提的是错的!!!!!!!!!!!

• @ 2015-10-18 20:00:50

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#define IN 100000000
const int maxn = 1000 + 5;
using namespace std;
int n,m,s,t,ll;
int a[maxn][maxn],num[maxn],f[maxn][maxn],dis[maxn],ans[maxn],pre[maxn];
bool vis[maxn];
void find(int x)
{
if(pre[x]==x){
printf("%d ",x);
return;
}
find(pre[x]);
printf("%d ",x);

}

void dijstra(int s)
{ int minn,k=0;
for(int i=1;i<=n;i++)dis[i]=f[s][i];
dis[s]=0;vis[s]=1;
for(int i=1;i<n;i++)
{
minn=IN;
for(int j=1;j<=n;j++)
if(!vis[j]&&dis[j]<minn){k=j;minn=dis[j];}
vis[k]=1;if(k==0)break;
for(int j=1;j<=n;j++)if(!vis[j]&&dis[j]>dis[k]+f[k][j]) {
dis[j]=dis[k]+f[k][j]; pre[j]=k;

}
}
}
int main()
{
int yy;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>f[i][j];
if(f[i][j]==0)
f[i][j]=IN;
}
for(int i=1;i<=n;i++)pre[i]=1;

int v=n;

dijstra(1);
find(n);
cout<<endl;
cout<<dis[n];
}

• @ 2015-09-28 19:19:15

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1001
using namespace std;
int f[maxn][maxn],c[maxn],pre[maxn];
bool b[maxn];
void find(int x)
{
if(pre[x]==x){
printf("%d ",x);
return;
}
find(pre[x]);
printf("%d ",x);

}
int main()
{
int n,m,i,j,x,minn,k;
scanf("%d",&n);
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
scanf("%d",&x);
if(x==0){
f[i][j]=709823562;
}
else{
f[i][j]=x;
}
}
}
memset(c,127/3,sizeof(c));
memset(b,false,sizeof(b));
b[1]=true;
for(i=1;i<=n;i++){
c[i]=f[1][i];
pre[i]=1;
}
for(i=1;i<=n;i++){
minn=210000000;
k=0;
for(j=1;j<=n;j++){
if(!b[j]&&c[j]<minn){
minn=c[j];
k=j;
}
}
if(k==0){
break;
}
b[k]=true;
for(j=1;j<=n;j++){
if(c[j]>c[k]+f[k][j]){
c[j]=c[k]+f[k][j];
pre[j]=k;
}
}
}
find(n);
printf("\n");
printf("%d",c[n]);
return 0;
}

• @ 2015-07-24 17:53:23

测试数据 #0: TimeLimitExceeded, time = 1031 ms, mem = 4280 KiB, score = 0
测试数据 #1: TimeLimitExceeded, time = 1031 ms, mem = 4288 KiB, score = 0
测试数据 #2: Accepted, time = 15 ms, mem = 4280 KiB, score = 15
测试数据 #3: TimeLimitExceeded, time = 1031 ms, mem = 4284 KiB, score = 0
测试数据 #4: Accepted, time = 62 ms, mem = 4284 KiB, score = 15
测试数据 #5: TimeLimitExceeded, time = 1015 ms, mem = 4288 KiB, score = 0
测试数据 #6: Accepted, time = 15 ms, mem = 4280 KiB, score = 5
测试数据 #7: Accepted, time = 437 ms, mem = 4284 KiB, score = 5
测试数据 #8: Accepted, time = 62 ms, mem = 4280 KiB, score = 5
测试数据 #9: TimeLimitExceeded, time = 1031 ms, mem = 4280 KiB, score = 0
TimeLimitExceeded, time = 5730 ms, mem = 4288 KiB, score = 45

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int sq[1010][1010];
int ming[1010][3];
int n;
void do_it(int k)
{
if(k==n)
return;
for(int i=1;i<=n;i++)
{
if(sq[k][i])
{
if(ming[i][1]>ming[k][1]+sq[k][i])
{
ming[i][1]=ming[k][1]+sq[k][i];
ming[i][2]=k;
do_it(i);
}
}
}
}
void findway(int a)
{
if(a==0)
return;
findway(ming[a][2]);
printf("%d ",a);
}
int main()
{

scanf("%d",&n);
for(int i=1;i<=n;i++)
{
ming[i][1]=INT_MAX;
for(int j=1;j<=n;j++)
{
int a;
scanf("%d",&a);
if(a==0)
continue;
sq[i][j]=a;
}
}
ming[1][1]=0;
do_it(1);
findway(ming[n][2]);
printf("%d\n%d",n,ming[n][1]);
}
编译成功

测试数据 #0: Accepted, time = 156 ms, mem = 8200 KiB, score = 15
测试数据 #1: Accepted, time = 390 ms, mem = 8200 KiB, score = 15
测试数据 #2: Accepted, time = 0 ms, mem = 8196 KiB, score = 15
测试数据 #3: Accepted, time = 374 ms, mem = 8196 KiB, score = 15
测试数据 #4: Accepted, time = 15 ms, mem = 8200 KiB, score = 15
测试数据 #5: Accepted, time = 358 ms, mem = 8200 KiB, score = 5
测试数据 #6: Accepted, time = 0 ms, mem = 8196 KiB, score = 5
测试数据 #7: Accepted, time = 46 ms, mem = 8200 KiB, score = 5
测试数据 #8: Accepted, time = 31 ms, mem = 8196 KiB, score = 5
测试数据 #9: Accepted, time = 296 ms, mem = 8200 KiB, score = 5
Accepted, time = 1666 ms, mem = 8200 KiB, score = 100
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int sq[1010][1010];
int dist[1010];
int queue[1001000];
int minpast[1010];
int n;
void findway(int a)
{
if(a==0)
return;
findway(minpast[a]);
printf("%d ",a);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
dist[i]=INT_MAX;
for(int j=1;j<=n;j++)
{
int a;
scanf("%d",&a);
if(a==0)
continue;
sq[i][j]=a;
}
}
dist[1]=0;
int front=1;
int back=2;
queue[front]=1;
for(;front<back;)
{
if(queue[front]==n)
{
front++;
continue;
}
for(int i=1;i<=n;i++)
{
if(sq[queue[front]][i])
if(dist[i]>dist[queue[front]]+sq[queue[front]][i])
{
dist[i]=dist[queue[front]]+sq[queue[front]][i];
queue[back++]=i;
minpast[i]=queue[front];
}
}front++;
}
findway(minpast[n]);
printf("%d",n);
printf("\n%d",dist[n]);
}

• @ 2015-07-03 12:14:42

P1635城市连接
Accepted

记录信息

评测状态 Accepted
题目 P1635 城市连接
递交时间 2015-07-03 12:13:53
代码语言 C++
评测机 VijosEx
消耗时间 777 ms
消耗内存 4288 KiB
评测时间 2015-07-03 12:13:55

评测结果

编译成功

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

测试数据 #1: Accepted, time = 187 ms, mem = 4288 KiB, score = 15

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

测试数据 #3: Accepted, time = 187 ms, mem = 4284 KiB, score = 15

测试数据 #4: Accepted, time = 15 ms, mem = 4288 KiB, score = 15

测试数据 #5: Accepted, time = 140 ms, mem = 4288 KiB, score = 5

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

测试数据 #7: Accepted, time = 31 ms, mem = 4288 KiB, score = 5

测试数据 #8: Accepted, time = 15 ms, mem = 4288 KiB, score = 5

测试数据 #9: Accepted, time = 140 ms, mem = 4288 KiB, score = 5

Accepted, time = 777 ms, mem = 4288 KiB, score = 100

代码

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

using namespace std;

int n;
int i , j , k;
int a[1000 + 10][1000 + 10];
int pre[1000 + 10];
int use[1000 + 10];
int dist[1000 + 10];
int p[1000 + 10];
int now;
queue < int > q;

int getpath( int x )
{
if( pre[x] < 0 )
return x;
p[i++] = x;
return getpath( pre[x] );
}

int main()
{
scanf( "%d" , &n );
for( i = 1 ; i <= n ; i++ )
pre[i] = -1;
for( i = 1 ; i <= n ; i++ )
for( j = 1 ; j <= n ; j++ )
scanf( "%d" , &a[i][j] );
for( i = 1 ; i <= n ; i++ )
for( j = 1 ; j <= n ; j++ )
if( !a[i][j] )
a[i][j] = 100000000;

for( i = 1 ; i <= n ; i++ )
dist[i] = 100000000;
q.push( 1 );
dist[1] = 0;
while( !q.empty() )
{
now = q.front();
q.pop();
use[ now ] = 0;
for( i = 1 ; i <= n ; i++ )
if( dist[i] > dist[now] + a[now][i] )
{
dist[i] = dist[now] + a[now][i];
pre[i] = now;
if( !use[i] )
{
use[i] = 1;
q.push(i);
}
}
}
i = 0;
getpath( n );
for( i = 0 ; p[i] != 0 ; i++ )
;
printf( "1" );
for( i-- ; i >= 0 ; i-- )
printf( " %d" , p[i] );
cout << endl;
printf( "%d\n" , dist[n] );
return 0;
}

• @ 2015-06-17 15:50:14

C++要注意用标准输入输出，否则TLE。。。在这里卡了好久。。。

• @ 2015-03-14 10:23:33

#include<stdio.h>//TLE
#include<string.h>
int dist[1010][1010],map[1010];
int min(int a,int b)
{
if(a>b)return b;
else return a;
}
int main()
{
int n,i,j;
int max=100000;
scanf("%d",&n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&dist[i][j]);
if(dist[i][j]==0)dist[i][j]=max;
}
}
int v[n];
memset(v,0,sizeof(v));
for(i=0;i<n;i++)map[i]=(i==0?0:max);
for(i=0;i<n;i++)
{
int y,x,m=max;
for(y=0;y<n;y++)
{
if(!v[y]&&map[y]<=m)
m=map[x=y];
}
v[x]=1;
for(y=0;y<n;y++)map[y]=min(map[y],map[x]+dist[x][y]);
}
int pre[n];
memset(pre,0,sizeof(pre));
int k=0;
int count=1;
int l=n-1;
pre[k++]=n;
while(count)
{
for(i=n-1;i>=0;i--)
{
if(i==0)count=0;
if(map[i]+dist[i][l]==map[l])
{
l=i;
pre[k++]=i+1;
}
}
}
for(i=k-1;i>=0;i--)
printf("%d ",pre[i]);
printf("\n");
printf("%d",map[n-1]);
return 0;
}
竟然会超时。。。。

• @ 2015-02-10 18:21:12
• 注意是**有向图**
• 虽然题目没说，但要知道必须**从 1 出发走到 n **
• 貌似没有无解情况

上代码（鄙人只会用 Dijkstra，膜拜下面那些大神～）

#include <stdio.h>
#include <limits.h>
int map[1000][1000];
int dijkstra[1000],searched[1000],path[1000];
void printPath(int index){
//递归输出路径。若 index==0 ，则意味着回溯到了起点，可以开始返回
if(index!=0)
printPath(path[index]);
//之所以要加一再输出是因为数组下标从零开始...
printf("%d ",index+1);
}
int main(){
int num;
int i,k,source,min,index;
scanf("%d",&num);
for(i=0;i<num;i++){
for(k=0;k<num;k++)
scanf("%d",&map[i][k]);
}
for(i=0;i<num;i++){
dijkstra[i]=LONG_MAX;
searched[i]=path[i]=0;
}
//设置起始点为0（即题目中的1）
path[0]=dijkstra[0]=0;
source=0;
for(i=1;i<num;i++){
//把源点标记为“已找过”
searched[source]=1;
min=LONG_MAX;
for(k=0;k<num;k++){
if(!searched[k]){
if(map[source][k]>0){
if(dijkstra[k] > dijkstra[source]+map[source][k]){
dijkstra[k]=dijkstra[source]+map[source][k];
//记录一下路径（到达k点最优路径的上一个节点，亦即源点source）
path[k]=source;
}
}
if(min>dijkstra[k]){
min=dijkstra[k];
index=k;
}
}
}
source=index;
}
//从终点回溯输出路径
printPath(num-1);
//输出最优解
printf("\n%d\n",dijkstra[num-1]);
return 0;
}

ID
1635

5

(无)

3419

1138

33%

2