【未完成】7-13 最短工期 (25 分)

韩旭051

发布于 2019-11-08 16:50:17

5980

文章被收录于专栏：刷题笔记刷题笔记

本文链接：https://blog.csdn.net/shiliang97/article/details/98790775

7-13 最短工期 (25 分)

一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。

输入格式：

首先第一行给出两个正整数：项目里程碑的数量 N（≤100）和任务总数 M。这里的里程碑从 0 到 N−1 编号。随后 M 行，每行给出一项任务的描述，格式为“任务起始里程碑任务结束里程碑工作时长”，三个数字均为非负整数，以空格分隔。

输出格式：

如果整个项目的安排是合理可行的，在一行中输出最早完工时间；否则输出"Impossible"。

输入样例 1：

输出样例 1：

输入样例 2：

输出样例 2：

Impossible

#include <bits/stdc++.h>
using namespace std;
struct node {
    int task,time;
};
node v[105];
int gm[105][105]= {0};
void init() {
    for(auto i:v)
        i.task=i.time=0;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    init();
    fill(gm[0],gm[0]+105*105,-1);
    int s,e,t;
    while(m--) {
        cin>>s>>e>>t;
        gm[s][e]=t;
        v[e].task++;
    }
    queue<int> q;
    for(int i=0; i<n; i++)
        if(v[i].task==0)
            q.push(i);
    while(!q.empty()) {
        int k=q.front();
        q.pop();
        for(int i=0; i<n; i++) {
            if(gm[k][i]>=0) {
                v[i].task--;
                if(v[i].time<v[k].time+gm[k][i])
                    v[i].time=v[k].time+gm[k][i];
                if(v[i].task==0)
                    q.push(i);
            }
        }
    }
    for(int i=0; i<n; i++) {
        if(v[i].task>0) {
            cout<<"Impossible";
            return 0;
        }
    }
    int res=0;
    for(int i=0; i<n; i++) {
        if(v[i].time>res)
            res=v[i].time;
    }
    cout<<res;
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/08/07 ，如有侵权请联系 cloudcommunity@tencent.com 删除

项目经理

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

项目经理

登录后参与评论

0 条评论

热度

【未完成】7-13 最短工期 (25 分)

【未完成】7-13 最短工期 (25 分)

7-13 最短工期 (25 分)

输入格式：

输出格式：

输入样例 1：

输出样例 1：

输入样例 2：

输出样例 2：

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐