网站开发设计报告/免费seo营销软件

描述

他们飘呀飘，飘呀飘，飘呀飘，飘呀飘~~~
经过七七八十一天的漂泊，残雪、夏夜和水手2011，终于到达了无尽的深渊--lcyz岛，正当他们准备从后门登陆时，突然半路杀出了一个程咬金--一个身高十二尺，腰围380的怪物。这正是传说中lcyz岛上的上古怪物，通道守护者，但是我们都叫他门卫。根据上古传说，只有拿到岛上的上古兵器毛剑，才可打败门卫。有了毛剑，神马都是浮云、、、
毛剑被珍藏在一个灰常隐秘的地下室里，残雪经过重重险阻，终于进入了剑冢，此时毛剑静静地插在一块由纯金打造的纯金上。残雪看见此景，不由感叹一声，好剑啊。又大喊一声：看我剑人合一。说罢，便伸手欲抽剑，但是，一个迷宫瞬间弹了出来（别问我怎么弹出来的-。-），这个迷宫情况如下：
迷宫中有n块区域，其中m条道路，如果从a区域到b区域存在一条道路的话，残雪要想通过这条道路，需要耗费一定的体力值，但是，某些道路上摆放着食物，残雪经过这些道路，可以补充一定的体力值，可以理解为权值为负的道路，现在残雪还要留着体力去打败门岗，需要用最小的体力值拿到毛剑，现在就请你帮助他们取出毛剑。残雪所处的位置在1区域，毛剑所处的位置在n区域。

输入格式

第一行：一个n，表示区域数目。
第二行：m，表示存在m条道路。
以下m行：
每行三个数：x、y、z
区域x、y的标号和他们之间耗费的体力值z

输出格式

从残雪到毛剑所耗费的最小体力（结果为负则为补充体力）。

测试样例1

输入

3 
3 
1 2 5 
2 3 10 
1 3 20 

输出

15

备注

对于30%的数据，有n<=1000，m<=2000
对于50%的数据，有n<=5000，m<=10000;
对于100%的数据，有n<=10000，m<=50000;
保证此题所涉及的所有数据都是整数。

题解

裸spfa就能过，单向边数据无负环，如果是双向边要怎么做？？请教神犇们

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define maxn 10005
#define maxm 50005
#define inf 1<<29
using namespace std;
queue<int> q;
int ecnt,n,m,dis[maxn],vis[maxn],head[maxn];
struct edge{
    int u,v,w,next,f;
}E[maxm*2];
void addedge(int u,int v,int w)
{
    E[++ecnt].u=u;
    E[ecnt].v=v;
    E[ecnt].w=w;
    E[ecnt].next=head[u];
    head[u]=ecnt;
}
void spfa()
{
    for(int i=1 ; i<=n ; ++i )
        dis[i]=inf;
    dis[1]=0;
    vis[1]=1;
    q.push(1);
    while(!q.empty())
    {
        int d=q.front();q.pop();
        vis[d]=0;
        for(int i=head[d] ; i ; i=E[i].next )
        {
            int v=E[i].v;
            int w=E[i].w;
            if(dis[v]>dis[d]+w)
            {
                dis[v]=dis[d]+w;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main()
{
    int u,v,w;
    scanf("%d%d",&n,&m);
    for(int i=1 ; i<=m ; ++i)
    {
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
    }
    spfa();
    printf("%d",dis[n]);
    return 0;
}