比赛 |
20110318 |
评测结果 |
C |
题目名称 |
工程规划 |
最终得分 |
0 |
用户昵称 |
苏轼 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-03-18 21:31:06 |
显示代码纯文本
#include <fstream>
#include <cstdlib>
#include <cstring>
#include <queue>
using namespace std;
typedef struct LIST_NODE {
int end, t;
LIST_NODE *next;
} *GLIST;
int N, M, count;
GLIST *lk;
ifstream fin("work.in");
ofstream fout("work.out");
inline void addway (const short a, const short b, const short t)
{
LIST_NODE *newnode = (LIST_NODE*)malloc(sizeof(LIST_NODE));
newnode->end = b;
newnode->t = t;
newnode->next = lk[a];
lk[a] = newnode;
}
void spfa (const int wh)
{
queue<int> q;
int dist[N];
bool boo[N];
memset(dist, 0x2F, sizeof(dist));
memset(boo, 0, sizeof(boo));
boo[wh] = true;
dist[wh] = 0;
q.push(wh);
while (!q.empty())
{
int curr = q.front();
q.pop();
for (LIST_NODE *pi=lk[curr]; pi; pi=pi->next)
{
count++;
if (dist[curr] + pi->t < dist[pi->end])
{
dist[pi->end] = dist[curr] + pi->t;
if (!boo[pi->end])
q.push(pi->end);
}
}
boo[curr] = false;
if (count > 7000000)
{
fout << "NO SOLUTION" << endl;
return;
}
}
int stime = dist[0];
for (int i=1; i<N; i++)
if (dist[i] < stime)
stime = dist[i];
for (int i=0; i<N; i++)
fout << dist[i]-stime << endl;
}
int main()
{
fin >> N >> M;
lk = (GLIST*)malloc(N*sizeof(GLIST));
memset(lk, 0, N*sizeof(GLIST));
int deg[N];
memset(deg, 0, sizeof(deg));
for (int i=0; i<M; i++)
{
int I, J, B;
fin >> I >> J >> B;
addway(J-1, I-1, B);
deg[I-1]++;
}
int mindeg = deg[0], k = 0;
for (int i=1; i<N; i++)
if (deg[i] < mindeg)
mindeg = deg[i],
k = i;
spfa(k);
fin.close();
fout.close();
return 0;
}