hdu 2544
求点1到点n的最短路 无向图
Sample Input
2 1 //结点数 边数
1 2 3 //u v w
3 3
1 2 5
2 3 5
3 1 2
0 0
Sample Output
3
2
堆优化Dijstra模板
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>
# include <queue>
# define LL long long
using namespace std ; const int INF=0x3f3f3f3f;
const int MAXN=;
struct qnode
{
int v;
int c;
qnode(int _v=,int _c=):v(_v),c(_c){}
bool operator <(const qnode &r)const
{
return c>r.c;
}
};
struct Edge
{
int v,cost;
Edge(int _v=,int _cost=):v(_v),cost(_cost){}
};
vector<Edge>E[MAXN];
bool vis[MAXN];
int dist[MAXN];
int n ;
void Dijkstra(int start)//点的编号从1开始
{
memset(vis,false,sizeof(vis));
for(int i=;i<=n;i++)dist[i]=INF;
priority_queue<qnode>que;
while(!que.empty())que.pop();
dist[start]=;
que.push(qnode(start,));
qnode tmp;
while(!que.empty())
{
tmp=que.top();
que.pop();
int u=tmp.v;
if(vis[u])continue;
vis[u]=true;
for(int i=;i<E[u].size();i++)
{
int v=E[tmp.v][i].v;
int cost=E[u][i].cost;
if(!vis[v]&&dist[v]>dist[u]+cost)
{
dist[v]=dist[u]+cost;
que.push(qnode(v,dist[v]));
}
}
}
}
void addedge(int u,int v,int w)
{
E[u].push_back(Edge(v,w));
} int main ()
{
// freopen("in.txt","r",stdin) ;
int m ;
while (scanf("%d %d" , &n , &m) !=EOF)
{
if (n== && m==)
break ;
int u , v , w ;
int i , j ;
for(i=;i<=n;i++)
E[i].clear(); while(m--)
{
scanf("%d%d%d" , &u , &v , &w) ;
addedge(u,v,w) ;
addedge(v,u,w) ;
}
Dijkstra() ;
printf("%d\n" , dist[n]) ;
} return ;
}
hdu 1874
输出最短需要行走的距离。如果不存在从S到T的路线，就输出-1.
这题有重边
Sample Input
3 3 //结点数 边数
0 1 1//u v w
0 2 3
1 2 1
0 2 //起点 终点
3 1
0 1 1
1 2
Sample Output
2
-1
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>
# define LL long long
using namespace std ; const int MAXN=;
const int INF=0x3f3f3f3f;
int n ;
bool vis[MAXN];
int cost[MAXN][MAXN] ;
int lowcost[MAXN] ;
int pre[MAXN];
void Dijkstra(int beg)
{
for(int i=;i<n;i++)
{
lowcost[i]=INF;vis[i]=false;pre[i]=-;
}
lowcost[beg]=;
for(int j=;j<n;j++)
{
int k=-;
int Min=INF;
for(int i=;i<n;i++)
if(!vis[i]&&lowcost[i]<Min)
{
Min=lowcost[i];
k=i;
}
if(k==-)
break ;
vis[k]=true;
for(int i=;i<n;i++)
if(!vis[i]&&lowcost[k]+cost[k][i]<lowcost[i])
{
lowcost[i]=lowcost[k]+cost[k][i];
pre[i]=k;
}
} } int main ()
{
// freopen("in.txt","r",stdin) ;
int m ;
while (scanf("%d %d" , &n , &m) !=EOF)
{ int u , v , w ;
int i , j ;
for (i = ; i < n ; i++)
for (j = ; j < n ; j++)
cost[i][j] = INF ;
while(m--)
{
scanf("%d%d%d" , &u , &v , &w) ;
if (w < cost[u][v]) //防止重边
{
cost[u][v] = w ;
cost[v][u] = w ;
}
}
scanf("%d %d" , &u , &v) ;
Dijkstra(u) ;
if (lowcost[v] != INF)
printf("%d\n" , lowcost[v]) ;
else
printf("-1\n") ;
} return ;
}
poj 2387
有重边 无向图
Sample Input
5 5 // m n
1 2 20 //u v w
2 3 30
3 4 20
4 5 20
1 5 100
Sample Output
90
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>
# define LL long long
using namespace std ; const int MAXN=;
const int INF=0x3f3f3f3f;
int n ;
bool vis[MAXN];
int cost[MAXN][MAXN] ;
int lowcost[MAXN] ;
int pre[MAXN];
void Dijkstra(int beg)
{
for(int i=;i<n;i++)
{
lowcost[i]=INF;vis[i]=false;pre[i]=-;
}
lowcost[beg]=;
for(int j=;j<n;j++)
{
int k=-;
int Min=INF;
for(int i=;i<n;i++)
if(!vis[i]&&lowcost[i]<Min)
{
Min=lowcost[i];
k=i;
}
if(k==-)
break ;
vis[k]=true;
for(int i=;i<n;i++)
if(!vis[i]&&lowcost[k]+cost[k][i]<lowcost[i])
{
lowcost[i]=lowcost[k]+cost[k][i];
pre[i]=k;
}
} } int main ()
{
// freopen("in.txt","r",stdin) ;
int m ;
while (scanf("%d %d" , &m , &n) !=EOF)
{ int u , v , w ;
int i , j ;
for (i = ; i < n ; i++)
for (j = ; j < n ; j++)
{
if (i == j)
cost[i][j] = ;
else
cost[i][j] = INF ;
}
while(m--)
{
scanf("%d%d%d" , &u , &v , &w) ;
if (w < cost[u-][v-]) //防止重边
{
cost[u-][v-] = w ;
cost[v-][u-] = w ;
}
}
Dijkstra(n-) ;
if (lowcost[] != INF)
printf("%d\n" , lowcost[]) ; } return ;
}