用spfa做，额，到目前为止做的题目都几乎是模板题，三四道都是改一下输入就了事了，不过针对题目而已，还真有选择的余地，这里一个是我的，额，内存开得太大了，主要是1000*1000的矩阵来保存一个图的信息，本来很明显的得用邻接表来储存的，，而且只保存有用的边，而且加上用队列优化，快了不少呢
对比一下俩个代码吧
用邻接表的：
#include<cstdio>
#include<iostream>
using namespace std;
#define N 4000
struct edge{
int v,next,cost;
edge(int _v=0 ,int _next=0,int _cost=0):v(_v),next(_next),cost(_cost){};
}e[N];
int dist[N];
int n,m,p[N],tot = 0;
void spfa(int s)
{
bool vist[N];
memset(vist,false ,sizeof(vist));
memset(dist,1,sizeof(dist));
dist[s] = 0;
int que[N];
int begin,end;
begin = end = 0;
que[end++] = s;
vist[s] = true;
while(begin<end)
{
int t = que[begin++];
vist[t] = false;
for(int j = p[t];j!=-1;j = e[j].next)
{
if(dist[e[j].v]>e[j].cost+dist[t])
{
dist[e[j].v] = e[j].cost+dist[t];
if(!vist[e[j].v])
{
vist[e[j].v] = true;
que[end++] = e[j].v;
}
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
tot = 0;
memset(p,-1,sizeof(p));
int a,b,c;
for(int i = 0;i<n;i++)
{
scanf("%d%d%d",&a,&b,&c);
e[tot]=edge(b,p[a],c);
p[a] = tot++;
e[tot]=edge(a,p[b],c);
p[b] = tot++;
}
spfa(1);
printf("%d\n",dist[m]);
}
}
直接用邻接矩阵保存的：
#include<iostream>
#define MAXINT 999999
using namespace std;
int m,n;
int dis[1001],Q[10010],vis[1001];
int map[1001][1001];
void SPFA(int n, int s)
{
// pri是队列头结点，end是队列尾结点
int i, pri, end, p;
memset(vis, 0, sizeof(vis));
for(int i=0; i<10010; ++i)
Q[i] = 0;
for (i=1; i<=n; i++)
dis[i] =MAXINT;
dis[s] = 0;
vis[s] = 1;
Q[1] = s; pri = 1; end = 2;
while (pri < end)
{
p = Q[pri];
for (i=1; i<=n; ++i)
{
//更新dis
if (dis[p]+map[p][i] < dis[i])
{
dis[i] = dis[p]+map[p][i];
if (!vis[i]) //未在队列中
{
Q[end++] = i;
vis[i] = 1;
}
}
}
vis[p] = 0; // 置出队的点为未标记
pri++;
}
}
int main()
{
while(cin>>m>>n)
{
int a,b,len;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
map[i][j]=MAXINT;
for(int i=1;i<=m;i++)
{
cin>>a>>b>>len;
if(map[a][b]>len)
{
map[a][b]=len;
map[b][a]=len;
}
}
SPFA(n,1);
cout<<dis[n]<<endl;
}
return 0;
}