Vijos:P1540月亮之眼

描述

吉儿是一家古董店的老板娘,由于她经营有道,小店开得红红火火。昨天,吉儿无意之中得到了散落民间几百年的珍宝—月亮之眼。吉儿深知“月亮之眼”价值连城:它是由许多珍珠相连而成的,工匠们用金线连接珍珠,每根金线连接两个珍珠;同时又对每根金线染上两种颜色,一半染成银白色,一半染成黛黑色。由于吉儿自小熟读古籍,所以还晓得“月亮之眼”的神秘传说:“月亮之眼”原是一个古代寺庙的宝物,原本是挂在佛堂的一根顶梁柱上的,整个宝物垂直悬挂,所有珍珠排成一线,且都镶嵌在柱子里,而每一根金线又都是绷紧的,并且金线的银白色一端始终在黛黑色一端的上方;然而,在一个月圆之夜,“月亮之眼”突然从柱里飞出,掉落下来,宝物本身完好无损,只是僧侣们再也无法以原样把“月亮之眼”嵌入柱子中了。吉儿望着这个神秘的宝物,回忆着童年读到的传说,顿时萌发出恢复“月亮之眼”的冲动,但是摆弄了几天依旧没有成功。

现在,要麻烦您来帮助吉儿完成这项使命。

您要设计一个程序,对于给定的“月亮之眼”进行周密分析,然后给出这串宝物几百年前嵌在佛堂顶梁柱上的排列模样。给定的“月亮之眼”有N个珍珠和P根金线,所有珍珠按一定顺序有了一个序号:1、2…、N。

格式

输入格式

输入数据包含一个“月亮之眼”的特征描述:
文件第一行有两个整数N和P,其中N表示宝物中的珍珠个数,P表示宝物中的金线根数;
以下P行描述珍珠连接情况:
文件第I+1行有三个整数,Ri1,Ri2,Li。其中Ri1表示第I根金线的银白色一端连接的珍珠序号;Ri2表示第I根金线的黛黑色一端连接的珍珠序号;Li表示第I根金线的长度。

输出格式

由于珍珠尺寸很小,所以几个珍珠可以同时镶嵌在一个位置上。

您的输出数据描述的是“月亮之眼”各个珍珠在顶梁柱上的位置,输出文件共N行:
第I行,一个整数S,它表示标号为I的珍珠在顶梁柱上距离最高位置珍珠的距离。

注意:若无解则输出仅一行,包含一个整数“-1”。

输入:

9 9
1 2 3
2 3 5
2 7 1
4 5 4
5 6 1
5 9 1
6 7 1
7 8 3
9 8 4

输出

2
5
10
0
4
5
6
9
5

思路:向上为负,向下为正,bfs求1号珍珠到每个珍珠的距离(spfa也可以),找出最小距离,就是最上面的那颗珍珠,设其为k.那么其他珍珠到珍珠k的距离为d[i]-d[k]

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int MAXN=505;
const int INF=0x7f7f7f7f;
struct Edge{
    int to,w;
    Edge(){}
    Edge(int  to,int w)
    {
        this->to=to;
        this->w=w;
    }
};
vector<Edge> mp[MAXN];
int d[MAXN],vis[MAXN];
int cnt[MAXN];
int n,m;
bool bfs(int u)
{
    for(int i=1;i<=n;i++)
    {
        d[i]=INF;
        vis[i]=0;
    }
    queue<int> que;
    d[u]=0;
    vis[u]=1;
    que.push(u);
    while(!que.empty())
    {
        int now=que.front();que.pop();
        for(int i=0;i<mp[now].size();i++)
        {
            Edge e=mp[now][i];
            int l=d[now]+e.w;
            if(vis[e.to]&&l!=d[e.to])
            {
                return false;
            }
            else if(!vis[e.to])
            {
                que.push(e.to);
                vis[e.to]=1;
                d[e.to]=l;
            }
        }
        
    }
    return true;
}

int main()
{
    
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        mp[u].push_back(Edge(v,w));
        mp[v].push_back(Edge(u,-w));
    }
    if(bfs(1))
    {
        int mn=INF;
        for(int i=1;i<=n;i++)
        {
            if(d[i]<mn)
            {
                mn=d[i];
            }
        }    
        for(int i=1;i<=n;i++)
        {
            d[i]-=mn;
        }
        for(int i=1;i<=n;i++)
        {
            printf("%d",d[i]);
            if(i!=n)
                printf("
");
        }
    }
    else
        printf("-1
");
    return 0;
}    
原文地址:https://www.cnblogs.com/program-ccc/p/5350736.html