最短路
Time Limit: 3000/1000MS (Java/Others)
Memory Limit: 65535/65535KB (Java/Others)
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的T-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？
Input
输入包括多组数据。
每组数据第一行是两个整数NN ,MM (N≤100N≤100 ,M≤10000M≤10000 )，NN 表示成都的大街上有几个路口，标号为11 的路口是商店所在地，标号为NN 的路口是赛场所在地，MM 则表示在成都有几条路。N=M=0N=M=0 表示输入结束。
接下来MM 行，每行包括33 个整数AA ,BB ,CC (1≤A1≤A ,B≤NB≤N ,1≤C≤10001≤C≤1000 ),表示在路口AA 与路口BB 之间有一条路，我们的工作人员需要CC 分钟的时间走过这条路。
输入保证至少存在11 条商店到赛场的路线。
Output
对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间。
Sample input and output
| Sample Input | Sample Output |
|---|---|
2 1 |
3 |
题意好理解，就是最短路。
最短路。。。传送门http://developer.51cto.com/art/201403/433874.htm
打训练赛的时候这个题wa了7次，最后也没写对，也是没谁了(；´д｀)ゞ
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=+;
const int INF=0x3f3f3f3f;
typedef long long ll;
int hh[N][N];
int n,m;
int gg(){ //关键
for(int h=;h<=n;h++)
for(int i=;i<=n;i++)
for(int j=;j<=n;j++) //这里当时写错了，j<=n写成j<=m了。。。
hh[i][j]=min(hh[i][j],hh[i][h]+hh[h][j]);
}
int main(){
int h,k,l;
while(~scanf("%d%d",&n,&m)&&(n||m)){
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
hh[i][j]=INF;
for(int i=;i<m;i++){
scanf("%d%d%d",&h,&k,&l);
if(l<hh[h][k])
hh[h][k]=hh[k][h]=l;
}
gg();
printf("%d\n",hh[][n]);
}
return ;
}
啊啊啊啊啊啊啊，还有一个思路可以写，spfa算法+链式前向星建图
然而，前向星有的看懂了，有的还很(O_O)?传送门http://www.cnblogs.com/Tovi/p/6194786.html
人家的代码，传送门http://blog.csdn.net/lvshubao1314/article/details/23034601
代码:
#include<string.h>
#include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;
const int maxn=1e5+;
const int INF=1e9;
struct node{
int b,w,next;
};
node edge[maxn];
int s,n,ip;
int head[maxn],que[maxn],visit[maxn],dis[maxn];
void add(int u,int v,int c){
edge[ip].b=v;edge[ip].w=c;edge[ip].next=head[u];head[u]=ip++;
}
void spfa(int start,int numpoint){
memset(visit,,sizeof(visit));
for(int i=;i<=numpoint;i++)
dis[i]=INF;
int front=-,tail=-;
dis[start]=;visit[start]=;que[++tail]=start;
int top,to,temp;
while(front!=tail){
if(++front>numpoint)front-=numpoint;
top=que[front];visit[top]=;
for(int p=head[top];p!=-;p=edge[p].next){
to=edge[p].b;temp=dis[top]+edge[p].w;
if(dis[to]>temp){
dis[to]=temp;
if(!visit[to]){
if(++tail>numpoint)tail-=numpoint;
que[tail]=to;
visit[to]=;
}
}
}
}
}
int main(){
int b,w,m,k;
while(~scanf("%d%d",&n,&m)){
if(m==&&n==)break;
int maxx=-;
memset(head,-,sizeof(head));
ip=;
for(int i=;i<=m;i++){
cin>>k>>b>>w;
if(k>maxx)maxx=k;
if(b>maxx)maxx=b;
add(k,b,w);
add(b,k,w);
}
spfa(,maxx);
printf("%d\n",dis[n]);
}
return ;
}
菜的掉渣，继续努力TAT