#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define Max 10005
#define inf 1<<28
using namespace std;
struct node
{
    int v,w;
};
int N,M;
vector<node>g[Max];
queue<int >q;
int visit[Max];
int dis[Max];
int spfa(int s,int e)
{
    int i,j;
    for(i=1;i<=N;i++)
    dis[i]=inf;
    dis[s]=0;
    q.push(s);
    visit[s]=1;
    while(!q.empty())
    {
        int temp=q.front();
        q.pop();
        visit[temp]=0;
        for(i=0;i<g[temp].size();i++)
        {
            int v=g[temp][i].v;
            int w=g[temp][i].w;
            if(dis[v]>dis[temp]+w)
            {
                dis[v]=dis[temp]+w;
                if(!visit[v])
                {
                    visit[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return dis[e];
}
int main()
{

    int i,j,k,l,n,m;
    int x,y,s;
    while(scanf("%d%d",&N,&M))
    {
        for(i=0;i<=N;i++)
        g[i].clear();
        if(N==0&&M==0)
        return 0;
        memset(visit,0,sizeof(visit));
        while(M--)
        {
            scanf("%d%d%d",&x,&y,&s);
            node t;
            t.v=y;
            t.w=s;
            g[x].push_back(t);
            t.v=x;
            g[y].push_back(t);
        }
        cout<<spfa(1,N)<<endl;
    }
    return 0;
}

invincible 2012-06-30 23:03 发表评论

#include <cstdio>
#include <algorithm>
using namespace std;
struct kdq
{
    int start,end;//起始和结束房间号对应的走廊距离
    bool visit;//判断是否已经计算
}time[505];
bool cmp(kdq a,kdq b)
{
    return a.start<b.start;
}
int main()
{
    int i,j,k,l,n,m;
    int T;
    cin>>T;
    int a,b;
    while(T--)
    {
        cin>>n;
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            a=(a+1)/2,b=(b+1)/2;//房间号对应的走廊距离
            time[i].start=a<b?a:b;
            time[i].end=a>b?a:b;
            time[i].visit=0;
        }
        sort(time,time+n,cmp);//按start从小到大排序
        int start=time[0].end;
        time[0].visit=1;
        int num=0;
        while(1)//贪心
        {
            num++;
            bool flag=0;
            for(i=0;i<n;i++)
            {
                if(!time[i].visit)
                {
                    if(time[i].start>start)
                    {
                        time[i].visit=1;
                        start=time[i].end;
                    }
                }
            }
            for(i=0;i<n;i++)
            {
                if(!time[i].visit)
                {
                    flag=1;
                    start=time[i].end;
                    time[i].visit=1;
                    break;
                }
            }

            if(!flag)
            break;
        }
        cout<<num*10<<endl;
    }
    return 0;
}

invincible 2012-06-30 22:55 发表评论