设为首页 - 加入收藏 焦点技术网
热搜:java
当前位置:首页 >

HDU 1874 畅通工程续

2014-06-28 17:28:00.0 Graph Theory 最短路 SPFA  
导读:终于遇到一个模版题了。怒套之前写的模版。#include#include#include#include#include#include#include#include#define INF 0xfffffffusing namespace std;int n,m;bool vis[201];int d[201];struct lx{ int v,c;};vectorg[201];void ...。。。

哭

终于遇到一个模版题了。

怒套之前写的模版。

#include#include#include#include#include#include#include#include#define INF 0xfffffffusing namespace std;int n,m;bool vis[201];int d[201];struct lx{    int v,c;};vectorg[201];void SPFA(int start,int thend){    for(int i=0; i<=n; i++)        d[i]=INF,vis[i]=0;    queueq;    vis[start]=1,d[start]=0;    q.push(start);    while(!q.empty())    {        int u=q.front();        q.pop();        vis[u]=0;        for(int j=0; jd[u]+c)            {                d[v]=d[u]+c;                if(!vis[v])                {                    vis[v]=1;                    q.push(v);                }            }        }    }    if(d[thend]>=INF)        puts("-1");    else        printf("%d\n",d[thend]);}int main(){    while(scanf("%d%d",&n,&m)!=EOF)    {        for(int i=0; i<=n; i++)            g[i].clear();        int start,thend;        while(m--)        {            int u,v,c;            scanf("%d%d%d",&u,&v,&c);            lx now;            now.c=c;            now.v=u,g[v].push_back(now);            now.v=v,g[u].push_back(now);        }        scanf("%d%d",&start,&thend);        SPFA(start,thend);    }}


(编辑: dongshimou)

网友评论