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;
}

#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****

迪杰特斯拉嘻嘻 记录路线的有一点点麻烦（也许是我太菜）
```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]);
}
```

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;
}

来个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--)

void Read(int&);

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

inline void init() {
    Read(n);
    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;
}

inline void Read(int &x) {
    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;
}

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
  readln(n);
  for i:=1 to n do
  for j:=1 to n do
  begin
    read(w[i,j]);
    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.

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
    readln(n);
    for i:=1 to n do
        for j:=1 to n do
            read(a[i,j]);
    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.

//弱弱的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;
}

裸地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;
}


数组开小了就太坑了！！害得我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;
}


裸的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;
}

此题数据太弱。上次手贱将运算符重载打错，小根堆变成大根堆居然还能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];
inline int read(){
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(){
n = read(); clr(last,0);
rep(i,1,n) rep(j,1,n){
z = read();
if (z) addedge(i,j,z);
}
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;
}

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

#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];
}

#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;
}

测试数据 #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]);
}

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;
}

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

#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;
}
竟然会超时。。。。

• 注意是**有向图**
• 虽然题目没说，但要知道必须**从 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;
}