>n>>m){ memset(a,6,sizeof(a)); memset(vis,0,sizeof(vis)); for(int i=0;i>t1>>t2>>t3; […]">

hdu1874 dijkstra

2017年02月24日 10点热度 0人点赞 0条评论

dijkstra算法,呵呵

代码

#include
#include
#include
using namespace std;
int main(){
   // freopen("1.txt","r",stdin);
int t1,t2,s,t,t3,n,m,dis[205],a[205][205];
bool vis[205];
while(cin>>n>>m){
        memset(a,6,sizeof(a));
        memset(vis,0,sizeof(vis));
    for(int i=0;i<m;i++){
    cin>>t1>>t2>>t3;
    a[t1][t2]=a[t2][t1]=min(a[t1][t2],t3);
    }
    for(int i=0;i<n;i++)
    a[i][i]=0;
    cin>>s>>t;
    memset(dis,6,sizeof(dis));
    for(int i=0;i<n;i++)
            dis[i]=a[s][i];
        dis[s]=0;
        vis[s]=1;
for(int i=1;i<n;i++){
    int k=-1;
    for(int i=0;i<n;i++)
        if(!vis[i]&&(k==-1||dis[k]>dis[i]))
        k=i;
    if(k==-1) break;
    vis[k]=1;
    for(int i=0;i<n;i++)
        if(!vis[i]&&dis[i]>dis[k]+a[k][i])
        dis[i]=dis[k]+a[k][i];
}
cout<<(dis[t]==dis[204]?-1:dis[t])<<endl;
}
}




bellman forde算法,呵呵
#include
#include
#include
struct node{
int a,b,w;}a[2005];
using namespace std;
int main(){
   // freopen("1.txt","r",stdin);
int n,m,dis[205],s,t;
while(cin>>n>>m){
    for(int i=0;i<m;i++){
        cin>>a[i].a>>a[i].b>>a[i].w;
        a[i+m].a=a[i].b;
        a[i+m].b=a[i].a;
        a[i+m].w=a[i].w;
    }
    memset(dis,6,sizeof(dis));
    cin>>s>>t;
bool flag;
dis[s]=0;
m*=2;
for(int i=1;i<n;i++){
    flag=1;
    for(int i=0;i<m;i++)
    if(dis[a[i].a]>dis[a[i].b]+a[i].w){
        flag=0;
        dis[a[i].a]=dis[a[i].b]+a[i].w;
    }
    if(flag) break;
}
cout<<(dis[t]==dis[204]?-1:dis[t])<<endl;
}
}

未经允许不得转载!hdu1874 dijkstra

update

纸上得来终觉浅, 绝知此事须躬行。